﻿<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3c.org/TR/1999/REC-html401-19991224/loose.dtd">
<!-- saved from url=(0080)mhtml:file://E:\sve-air\documentacion\RSA - Wikipedia, the free encyclopedia.mht -->
<HTML lang=en dir=ltr xmlns="http://www.w3.org/1999/xhtml"><HEAD><TITLE>RSA - Wikipedia, the free encyclopedia</TITLE>
<META http-equiv=Content-Type content="text/html; charset=UTF-8">
<META http-equiv=Content-Style-Type content=text/css>
<META content="MSHTML 6.00.6000.17080" name=GENERATOR><LINK 
title="Edit this page" href="/w/index.php?title=RSA&amp;action=edit" 
type=application/x-wiki rel=alternate><LINK title="Edit this page" 
href="/w/index.php?title=RSA&amp;action=edit" rel=edit><LINK 
href="http://en.wikipedia.org/apple-touch-icon.png" rel=apple-touch-icon><LINK 
href="/favicon.ico" rel="shortcut icon"><LINK title="Wikipedia (en)" 
href="/w/opensearch_desc.php" type=application/opensearchdescription+xml 
rel=search><LINK href="http://en.wikipedia.org/w/api.php?action=rsd" 
type=application/rsd+xml rel=EditURI><LINK 
href="http://creativecommons.org/licenses/by-sa/3.0/" rel=copyright><LINK 
title="Wikipedia Atom feed" 
href="/w/index.php?title=Special:RecentChanges&amp;feed=atom" 
type=application/atom+xml rel=alternate><LINK media=all 
href="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/load.css" 
type=text/css rel=stylesheet>
<STYLE type=text/css media=all>A.new {
	COLOR: #ba0000
}
#quickbar A.new {
	COLOR: #ba0000
}
</STYLE>

<META content="" name=ResourceLoaderDynamicStyles><LINK media=all 
href="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/load(1).css" 
type=text/css rel=stylesheet><LINK media=all 
href="http://bits.wikimedia.org/en.wikipedia.org/load.php?debug=false&amp;lang=en&amp;modules=user&amp;only=styles&amp;skin=vector&amp;version=19700101T000001Z" 
type=text/css rel=stylesheet><!--[if lt IE 7]><style type="text/css">body{behavior:url("/w/skins-1.17/vector/csshover.min.htc")}</style><![endif]--></HEAD>
<BODY class="mediawiki ltr ns-0 ns-subject page-RSA skin-vector">
<DIV class=noprint id=mw-page-base></DIV>
<DIV class=noprint id=mw-head-base></DIV><!-- content -->
<DIV id=content><A id=top></A>
<DIV id=mw-js-message style="DISPLAY: none"></DIV><!-- sitenotice -->
<DIV id=siteNotice><!-- centralNotice loads here -->
<SCRIPT type=text/javascript>
/* <![CDATA[ */
document.writeln("\x3cdiv id=\"localNotice\"\x3e\x3cp\x3e\x3c/p\x3e\n\x3c/div\x3e");
/* ]]> */
</SCRIPT>
</DIV><!-- /sitenotice --><!-- firstHeading -->
<H1 class=firstHeading id=firstHeading>RSA</H1><!-- /firstHeading --><!-- bodyContent -->
<DIV id=bodyContent><!-- tagline -->
<DIV id=siteSub>From Wikipedia, the free encyclopedia</DIV><!-- /tagline --><!-- subtitle -->
<DIV id=contentSub></DIV><!-- /subtitle --><!-- jumpto -->
<DIV id=jump-to-nav>Jump to: <A 
href="http://en.wikipedia.org/wiki/RSA#mw-head">navigation</A>, <A 
href="http://en.wikipedia.org/wiki/RSA#p-search">search</A> </DIV><!-- /jumpto --><!-- bodytext -->
<DIV class=dablink>This article is about an algorithm for public-key encryption. 
For the U.S. encryption and network security company, see <A class=mw-redirect 
title="RSA Security" href="http://en.wikipedia.org/wiki/RSA_Security">RSA 
Security</A>. For the Republic of South Africa, see <A 
href="http://en.wikipedia.org/wiki/South_Africa">South Africa</A>. For other 
uses, see <A href="http://en.wikipedia.org/wiki/RSA_(disambiguation)">RSA 
(disambiguation)</A>.</DIV>
<P>In <A href="http://en.wikipedia.org/wiki/Cryptography">cryptography</A>, 
<B>RSA</B> (which stands for <A title="Ron Rivest" 
href="http://en.wikipedia.org/wiki/Ron_Rivest">Rivest</A>, <A title="Adi Shamir" 
href="http://en.wikipedia.org/wiki/Adi_Shamir">Shamir</A> and <A 
title="Leonard Adleman" 
href="http://en.wikipedia.org/wiki/Leonard_Adleman">Adleman</A> who first 
publicly described it) is an <A 
href="http://en.wikipedia.org/wiki/Algorithm">algorithm</A> for <A 
href="http://en.wikipedia.org/wiki/Public-key_cryptography">public-key 
cryptography</A>.<SUP class=reference id=cite_ref-rsa_0-0><A 
href="http://en.wikipedia.org/wiki/RSA#cite_note-rsa-0"><SPAN>[</SPAN>1<SPAN>]</SPAN></A></SUP> 
It is the first algorithm known to be suitable for <A title="Digital signature" 
href="http://en.wikipedia.org/wiki/Digital_signature">signing</A> as well as 
encryption, and was one of the first great advances in public key cryptography. 
RSA is widely used in <A 
href="http://en.wikipedia.org/wiki/Electronic_commerce">electronic commerce</A> 
protocols, and is believed to be secure given sufficiently long keys and the use 
of up-to-date implementations.</P>
<TABLE class=toc id=toc>
  <TBODY>
  <TR>
    <TD>
      <DIV id=toctitle>
      <H2>Contents</H2></DIV>
      <UL>
        <LI class="toclevel-1 tocsection-1"><A 
        href="http://en.wikipedia.org/wiki/RSA#History"><SPAN 
        class=tocnumber>1</SPAN> <SPAN class=toctext>History</SPAN></A> 
        <LI class="toclevel-1 tocsection-2"><A 
        href="http://en.wikipedia.org/wiki/RSA#Operation"><SPAN 
        class=tocnumber>2</SPAN> <SPAN class=toctext>Operation</SPAN></A> 
        <UL>
          <LI class="toclevel-2 tocsection-3"><A 
          href="http://en.wikipedia.org/wiki/RSA#Key_generation"><SPAN 
          class=tocnumber>2.1</SPAN> <SPAN class=toctext>Key 
          generation</SPAN></A> 
          <LI class="toclevel-2 tocsection-4"><A 
          href="http://en.wikipedia.org/wiki/RSA#Encryption"><SPAN 
          class=tocnumber>2.2</SPAN> <SPAN class=toctext>Encryption</SPAN></A> 
          <LI class="toclevel-2 tocsection-5"><A 
          href="http://en.wikipedia.org/wiki/RSA#Decryption"><SPAN 
          class=tocnumber>2.3</SPAN> <SPAN class=toctext>Decryption</SPAN></A> 
          <LI class="toclevel-2 tocsection-6"><A 
          href="http://en.wikipedia.org/wiki/RSA#A_worked_example"><SPAN 
          class=tocnumber>2.4</SPAN> <SPAN class=toctext>A worked 
          example</SPAN></A> 
          <LI class="toclevel-2 tocsection-7"><A 
          href="http://en.wikipedia.org/wiki/RSA#Using_the_Chinese_remainder_algorithm"><SPAN 
          class=tocnumber>2.5</SPAN> <SPAN class=toctext>Using the Chinese 
          remainder algorithm</SPAN></A> 
          <LI class="toclevel-2 tocsection-8"><A 
          href="http://en.wikipedia.org/wiki/RSA#Attacks_against_plain_RSA"><SPAN 
          class=tocnumber>2.6</SPAN> <SPAN class=toctext>Attacks against plain 
          RSA</SPAN></A> 
          <LI class="toclevel-2 tocsection-9"><A 
          href="http://en.wikipedia.org/wiki/RSA#Padding_schemes"><SPAN 
          class=tocnumber>2.7</SPAN> <SPAN class=toctext>Padding 
          schemes</SPAN></A> 
          <LI class="toclevel-2 tocsection-10"><A 
          href="http://en.wikipedia.org/wiki/RSA#Signing_messages"><SPAN 
          class=tocnumber>2.8</SPAN> <SPAN class=toctext>Signing 
          messages</SPAN></A> </LI></UL>
        <LI class="toclevel-1 tocsection-11"><A 
        href="http://en.wikipedia.org/wiki/RSA#Security_and_practical_considerations"><SPAN 
        class=tocnumber>3</SPAN> <SPAN class=toctext>Security and practical 
        considerations</SPAN></A> 
        <UL>
          <LI class="toclevel-2 tocsection-12"><A 
          href="http://en.wikipedia.org/wiki/RSA#Integer_factorization_and_RSA_problem"><SPAN 
          class=tocnumber>3.1</SPAN> <SPAN class=toctext>Integer factorization 
          and RSA problem</SPAN></A> 
          <LI class="toclevel-2 tocsection-13"><A 
          href="http://en.wikipedia.org/wiki/RSA#Key_generation_2"><SPAN 
          class=tocnumber>3.2</SPAN> <SPAN class=toctext>Key 
          generation</SPAN></A> 
          <LI class="toclevel-2 tocsection-14"><A 
          href="http://en.wikipedia.org/wiki/RSA#Timing_attacks"><SPAN 
          class=tocnumber>3.3</SPAN> <SPAN class=toctext>Timing 
          attacks</SPAN></A> 
          <LI class="toclevel-2 tocsection-15"><A 
          href="http://en.wikipedia.org/wiki/RSA#Adaptive_chosen_ciphertext_attacks"><SPAN 
          class=tocnumber>3.4</SPAN> <SPAN class=toctext>Adaptive chosen 
          ciphertext attacks</SPAN></A> 
          <LI class="toclevel-2 tocsection-16"><A 
          href="http://en.wikipedia.org/wiki/RSA#Side-channel_analysis_attacks"><SPAN 
          class=tocnumber>3.5</SPAN> <SPAN class=toctext>Side-channel analysis 
          attacks</SPAN></A> </LI></UL>
        <LI class="toclevel-1 tocsection-17"><A 
        href="http://en.wikipedia.org/wiki/RSA#Proofs_of_correctness"><SPAN 
        class=tocnumber>4</SPAN> <SPAN class=toctext>Proofs of 
        correctness</SPAN></A> 
        <UL>
          <LI class="toclevel-2 tocsection-18"><A 
          href="http://en.wikipedia.org/wiki/RSA#Concise_proof_using_Euler.27s_Theorem"><SPAN 
          class=tocnumber>4.1</SPAN> <SPAN class=toctext>Concise proof using 
          Euler's Theorem</SPAN></A> 
          <LI class="toclevel-2 tocsection-19"><A 
          href="http://en.wikipedia.org/wiki/RSA#Proof_using_Fermat.27s_Little_Theorem_and_Chinese_Remainder_Theorem"><SPAN 
          class=tocnumber>4.2</SPAN> <SPAN class=toctext>Proof using Fermat's 
          Little Theorem and Chinese Remainder Theorem</SPAN></A> </LI></UL>
        <LI class="toclevel-1 tocsection-20"><A 
        href="http://en.wikipedia.org/wiki/RSA#See_also"><SPAN 
        class=tocnumber>5</SPAN> <SPAN class=toctext>See also</SPAN></A> 
        <LI class="toclevel-1 tocsection-21"><A 
        href="http://en.wikipedia.org/wiki/RSA#Notes"><SPAN 
        class=tocnumber>6</SPAN> <SPAN class=toctext>Notes</SPAN></A> 
        <LI class="toclevel-1 tocsection-22"><A 
        href="http://en.wikipedia.org/wiki/RSA#References"><SPAN 
        class=tocnumber>7</SPAN> <SPAN class=toctext>References</SPAN></A> 
        <LI class="toclevel-1 tocsection-23"><A 
        href="http://en.wikipedia.org/wiki/RSA#External_links"><SPAN 
        class=tocnumber>8</SPAN> <SPAN class=toctext>External links</SPAN></A> 
        </LI></UL></TD></TR></TBODY></TABLE>
<H2><SPAN class=editsection>[<A title="Edit section: History" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=1">edit</A>]</SPAN> 
<SPAN class=mw-headline id=History>History</SPAN></H2>
<P><A href="http://en.wikipedia.org/wiki/Clifford_Cocks">Clifford Cocks</A>, a 
British <A href="http://en.wikipedia.org/wiki/Mathematician">mathematician</A> 
working for the <A title="United Kingdom" 
href="http://en.wikipedia.org/wiki/United_Kingdom">UK</A> intelligence agency <A 
title="Government Communications Headquarters" 
href="http://en.wikipedia.org/wiki/Government_Communications_Headquarters">GCHQ</A>, 
described an equivalent system in an internal document in 1973, but given the 
relatively expensive computers needed to implement it at the time, it was mostly 
considered a curiosity and, as far as is publicly known, was never deployed. His 
discovery, however, was not revealed until 1998 due to its top-secret 
classification, and Rivest, Shamir, and Adleman devised RSA independently of 
Cocks' work.</P>
<DIV class="thumb tright">
<DIV class=thumbinner style="WIDTH: 177px"><A class=image 
href="http://en.wikipedia.org/wiki/File:Adi_Shamir_2009.jpg"><IMG 
class=thumbimage height=263 alt="" 
src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht144(1).tmp" 
width=175></A> 
<DIV class=thumbcaption>
<DIV class=magnify><A class=internal title=Enlarge 
href="http://en.wikipedia.org/wiki/File:Adi_Shamir_2009.jpg"><IMG height=11 
alt="" 
src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht147(1).tmp" 
width=15></A></DIV>Adi Shamir, one of the authors of RSA: <A title="Ron Rivest" 
href="http://en.wikipedia.org/wiki/Ron_Rivest">Rivest</A>, <A title="Adi Shamir" 
href="http://en.wikipedia.org/wiki/Adi_Shamir">Shamir</A> and <A 
title="Leonard Adleman" 
href="http://en.wikipedia.org/wiki/Leonard_Adleman">Adleman</A></DIV></DIV></DIV>
<P>The RSA algorithm was publicly described in 1978 by <A 
href="http://en.wikipedia.org/wiki/Ron_Rivest">Ron Rivest</A>, <A 
href="http://en.wikipedia.org/wiki/Adi_Shamir">Adi Shamir</A>, and <A 
href="http://en.wikipedia.org/wiki/Leonard_Adleman">Leonard Adleman</A> at <A 
title="Massachusetts Institute of Technology" 
href="http://en.wikipedia.org/wiki/Massachusetts_Institute_of_Technology">MIT</A>; 
the letters <B>RSA</B> are the initials of their surnames, listed in the same 
order as on the paper.<SUP class=reference id=cite_ref-SIAM_1-0><A 
href="http://en.wikipedia.org/wiki/RSA#cite_note-SIAM-1"><SPAN>[</SPAN>2<SPAN>]</SPAN></A></SUP></P>
<P><A title="Massachusetts Institute of Technology" 
href="http://en.wikipedia.org/wiki/Massachusetts_Institute_of_Technology">MIT</A> 
was granted <SPAN><A class="external text" 
href="http://www.google.com/patents?vid=4405829" rel=nofollow>U.S. Patent 
4,405,829</A></SPAN> for a "Cryptographic communications system and method" that 
used the algorithm in 1983. The patent would have expired on September 21, 2000 
(the <A href="http://en.wikipedia.org/wiki/Term_of_patent">term of patent</A> 
was 17 years at the time), but the algorithm was released to the public domain 
by <A class=mw-redirect title="RSA Security" 
href="http://en.wikipedia.org/wiki/RSA_Security">RSA Security</A> on 6 September 
2000, two weeks earlier.<SUP class=reference id=cite_ref-2><A 
href="http://en.wikipedia.org/wiki/RSA#cite_note-2"><SPAN>[</SPAN>3<SPAN>]</SPAN></A></SUP> 
Since a paper describing the algorithm had been published in August 1977,<SUP 
class=reference id=cite_ref-SIAM_1-1><A 
href="http://en.wikipedia.org/wiki/RSA#cite_note-SIAM-1"><SPAN>[</SPAN>2<SPAN>]</SPAN></A></SUP> 
prior to the December 1977 <A class=mw-redirect title="Filing date" 
href="http://en.wikipedia.org/wiki/Filing_date">filing date</A> of the <A 
href="http://en.wikipedia.org/wiki/Patent_application">patent application</A>, 
regulations in much of the rest of the world precluded <A title=Patent 
href="http://en.wikipedia.org/wiki/Patent">patents</A> elsewhere and only the <A 
title="United States" href="http://en.wikipedia.org/wiki/United_States">US</A> 
patent was granted. Had Cocks' work been publicly known, a patent in the US 
might not have been possible.</P>
<P>From the <A class=mw-redirect title="Derwent World Patent Index" 
href="http://en.wikipedia.org/wiki/Derwent_World_Patent_Index">DWPI</A>'s 
abstract of the patent,</P>
<BLOCKQUOTE>
  <P>The system includes a communications channel coupled to at least one 
  terminal having an encoding device and to at least one terminal having a 
  decoding device. A message-to-be-transferred is enciphered to ciphertext at 
  the encoding terminal by encoding the message as a number M in a predetermined 
  set. That number is then raised to a first predetermined power (associated 
  with the intended receiver) and finally computed. The remainder or residue, C, 
  is... computed when the exponentiated number is divided by the product of two 
  predetermined prime numbers (associated with the intended 
receiver).</P></BLOCKQUOTE>
<H2><SPAN class=editsection>[<A title="Edit section: Operation" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=2">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Operation>Operation</SPAN></H2>
<P>The RSA algorithm involves three steps: <A title="Key (cryptography)" 
href="http://en.wikipedia.org/wiki/Key_(cryptography)">key</A> generation, 
encryption and decryption.</P>
<H3><SPAN class=editsection>[<A title="Edit section: Key generation" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=3">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Key_generation>Key generation</SPAN></H3>
<P>RSA involves a <B>public key</B> and a <B>private key.</B> The public key can 
be known to everyone and is used for encrypting messages. Messages encrypted 
with the public key can only be decrypted using the private key. The keys for 
the RSA algorithm are generated the following way:</P>
<OL>
  <LI>Choose two distinct <A title="Prime number" 
  href="http://en.wikipedia.org/wiki/Prime_number">prime numbers</A> <I>p</I> 
  and <I>q</I>. 
  <UL>
    <LI>For security purposes, the integers <I>p</I> and <I>q</I> should be 
    chosen at random, and should be of similar bit-length. Prime integers can be 
    efficiently found using a <A 
    href="http://en.wikipedia.org/wiki/Primality_test">primality test</A>. 
  </LI></UL>
  <LI>Compute <SPAN style="WHITE-SPACE: nowrap"><I>n</I> = <I>pq</I>.</SPAN> 
  <UL>
    <LI><I>n</I> is used as the <A title="Modular arithmetic" 
    href="http://en.wikipedia.org/wiki/Modular_arithmetic">modulus</A> for both 
    the public and private keys </LI></UL>
  <LI>Compute <SPAN style="WHITE-SPACE: nowrap">φ(<I>n</I>) = 
  (<I>p</I> – 1)(<I>q</I> – 1)</SPAN>, where φ is <A 
  href="http://en.wikipedia.org/wiki/Euler's_totient_function">Euler's totient 
  function</A>. 
  <LI>Choose an integer <I>e</I> such that <SPAN style="WHITE-SPACE: nowrap">1 
  &lt; <I>e</I> &lt; φ(<I>n</I>)</SPAN> and <SPAN 
  style="WHITE-SPACE: nowrap">gcd(<I>e</I>,φ(<I>n</I>)) = 1</SPAN>, i.e. 
  <I>e</I> and φ(<I>n</I>) are <A 
  href="http://en.wikipedia.org/wiki/Coprime">coprime</A>. 
  <UL>
    <LI><I>e</I> is released as the public key exponent. 
    <LI><I>e</I> having a short <A class=new 
    title="Bit-length (page does not exist)" 
    href="http://en.wikipedia.org/w/index.php?title=Bit-length&amp;action=edit&amp;redlink=1">bit-length</A> 
    and small <A href="http://en.wikipedia.org/wiki/Hamming_weight">Hamming 
    weight</A> results in more efficient encryption - most commonly 0x10001 = 
    65537. However, small values of <I>e</I> (such as 3) have been shown to be 
    less secure in some settings.<SUP class=reference id=cite_ref-Boneh_3-0><A 
    href="http://en.wikipedia.org/wiki/RSA#cite_note-Boneh-3"><SPAN>[</SPAN>4<SPAN>]</SPAN></A></SUP> 
    </LI></UL>
  <LI>Determine <SPAN style="WHITE-SPACE: nowrap"><I>d</I> = 
  <I>e</I><SUP>–1</SUP> mod φ(<I>n</I>)</SPAN>; i.e. <I>d</I> is the <A 
  title="Modular multiplicative inverse" 
  href="http://en.wikipedia.org/wiki/Modular_multiplicative_inverse">multiplicative 
  inverse</A> of <SPAN style="WHITE-SPACE: nowrap"><I>e</I> mod 
  φ(<I>n</I>)</SPAN>. 
  <UL>
    <LI>This is often computed using the <A 
    href="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm">extended 
    Euclidean algorithm</A>. 
    <LI><I>d</I> is kept as the private key exponent. </LI></UL></LI></OL>
<P>The <B>public key</B> consists of the modulus <I>n</I> and the public (or 
encryption) exponent <I>e</I>. The <B>private key</B> consists of the private 
(or decryption) exponent <I>d</I> which must be kept secret.</P>
<P>Notes:</P>
<UL>
  <LI>An alternative, used by <A title=PKCS1 
  href="http://en.wikipedia.org/wiki/PKCS1">PKCS#1</A>, is to choose <I>d</I> 
  matching <SPAN style="WHITE-SPACE: nowrap"><I>de</I> ≡ 1 mod λ</SPAN> with 
  <SPAN style="WHITE-SPACE: nowrap">λ = lcm(<I>p</I> − 1,<I>q</I> − 1)</SPAN>, 
  where lcm is the <A 
  href="http://en.wikipedia.org/wiki/Least_common_multiple">least common 
  multiple</A>. Using λ instead of φ(<I>n</I>) allows more choices for <I>d</I>. 
  λ can also be defined using the <A 
  href="http://en.wikipedia.org/wiki/Carmichael_function">Carmichael 
  function</A>, λ(<I>n</I>). 
  <LI>The <A class=new title="ANSI X9.31 (page does not exist)" 
  href="http://en.wikipedia.org/w/index.php?title=ANSI_X9.31&amp;action=edit&amp;redlink=1">ANSI 
  X9.31</A> standard prescribes, <A class=mw-redirect title=P1363 
  href="http://en.wikipedia.org/wiki/P1363">IEEE 1363</A> describes, and <A 
  title=PKCS1 href="http://en.wikipedia.org/wiki/PKCS1">PKCS#1</A> allows, that 
  <I>p</I> and <I>q</I> match additional requirements: be <A 
  title="Strong prime" href="http://en.wikipedia.org/wiki/Strong_prime">strong 
  primes</A>, and be different enough that <A class=mw-redirect 
  title="Fermat factorization" 
  href="http://en.wikipedia.org/wiki/Fermat_factorization">Fermat 
  factorization</A> fails. </LI></UL>
<H3><SPAN class=editsection>[<A title="Edit section: Encryption" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=4">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Encryption>Encryption</SPAN></H3>
<P><A title="Alice and Bob" 
href="http://en.wikipedia.org/wiki/Alice_and_Bob">Alice</A> transmits her public 
key <SPAN class=texhtml>(<I>n</I>,<I>e</I>)</SPAN> to <A title="Alice and Bob" 
href="http://en.wikipedia.org/wiki/Alice_and_Bob">Bob</A> and keeps the private 
key secret. Bob then wishes to send message <B>M</B> to Alice.</P>
<P>He first turns <B>M</B> into an integer <SPAN class=texhtml>0 &lt; <I>m</I> 
&lt; <I>n</I></SPAN> by using an agreed-upon reversible protocol known as a <A 
href="http://en.wikipedia.org/wiki/RSA#Padding_schemes">padding scheme</A>. He 
then computes the ciphertext <SPAN class=texhtml><I>c</I></SPAN> corresponding 
to</P>
<DL>
  <DD><SPAN class=texhtml><I>c</I> = <I>m</I><SUP><I>e</I></SUP>(mod 
  <I>n</I>)</SPAN>. </DD></DL>
<P>This can be done quickly using the method of <A 
href="http://en.wikipedia.org/wiki/Exponentiation_by_squaring">exponentiation by 
squaring</A>. Bob then transmits <SPAN class=texhtml><I>c</I></SPAN> to 
Alice.</P>
<H3><SPAN class=editsection>[<A title="Edit section: Decryption" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=5">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Decryption>Decryption</SPAN></H3>
<P>Alice can recover <SPAN class=texhtml><I>m</I></SPAN> from <SPAN 
class=texhtml><I>c</I></SPAN> by using her private key exponent <SPAN 
class=texhtml><I>d</I></SPAN> via computing</P>
<DL>
  <DD><SPAN class=texhtml><I>m</I> = <I>c</I><SUP><I>d</I></SUP>(mod 
  <I>n</I>)</SPAN>. </DD></DL>
<P>Given <SPAN class=texhtml><I>m</I></SPAN>, she can recover the original 
message <B>M</B> by reversing the padding scheme.</P>
<P>(In practice, there are more efficient methods of calculating <SPAN 
class=texhtml><I>c</I><SUP><I>d</I></SUP></SPAN> using the pre computed values 
below.)</P>
<H3><SPAN class=editsection>[<A title="Edit section: A worked example" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=6">edit</A>]</SPAN> 
<SPAN class=mw-headline id=A_worked_example>A worked example</SPAN></H3>
<P>Here is an example of RSA encryption and decryption. The parameters used here 
are artificially small, but one can also <A class=extiw 
title="wikibooks:Transwiki:Generate a keypair using OpenSSL" 
href="http://en.wikibooks.org/wiki/Transwiki:Generate_a_keypair_using_OpenSSL">use 
OpenSSL to generate and examine a real keypair</A>.</P>
<OL>
  <LI>Choose two distinct prime numbers, such as 
  <DL>
    <DD><SPAN class=texhtml><I>p</I> = 61</SPAN> and <SPAN 
    class=texhtml><I>q</I> = 53</SPAN>. </DD></DL>
  <LI>Compute <SPAN class=texhtml><I>n</I> = <I>p</I><I>q</I></SPAN> giving 
  <DL>
    <DD><SPAN class=texhtml><I>n</I> = 61(53) = 3233</SPAN>. </DD></DL>
  <LI>Compute the <A class=mw-redirect title=Totient 
  href="http://en.wikipedia.org/wiki/Totient">totient</A> of the product as 
  <SPAN class=texhtml>φ(<I>n</I>) = (<I>p</I> − 1)(<I>q</I> − 1)</SPAN> giving 
  <DL>
    <DD><SPAN class=texhtml>φ(3233) = (61 − 1)(53 − 1) = 3120</SPAN>. </DD></DL>
  <LI>Choose any number <SPAN class=texhtml>1 &lt; <I>e</I> &lt; 3120</SPAN> 
  that is <A href="http://en.wikipedia.org/wiki/Coprime">coprime</A> to 3120. 
  Choosing a prime number for <SPAN class=texhtml><I>e</I></SPAN> leaves us only 
  to check that <SPAN class=texhtml><I>e</I></SPAN> is not a divisor of 3120. 
  <DL>
    <DD>Let <SPAN class=texhtml><I>e</I> = 17</SPAN>. </DD></DL>
  <LI>Compute <SPAN class=texhtml><I>d</I></SPAN>, the <A 
  href="http://en.wikipedia.org/wiki/Modular_multiplicative_inverse">modular 
  multiplicative inverse</A> of <SPAN class=texhtml><I>e</I>(mod 
  φ(<I>n</I>))</SPAN> yielding 
  <DL>
    <DD><SPAN class=texhtml><I>d</I> = 2753</SPAN>. </DD></DL></LI></OL>
<P>The <B>public key</B> is (<SPAN class=texhtml><I>n</I> = 3233</SPAN>, <SPAN 
class=texhtml><I>e</I> = 17</SPAN>). For a padded <A 
href="http://en.wikipedia.org/wiki/Plaintext">plaintext</A> message <SPAN 
class=texhtml><I>m</I></SPAN>, the encryption function is <SPAN 
class=texhtml><I>m</I><SUP>17</SUP>(mod 3233)</SPAN>.</P>
<P>The <B>private key</B> is (<SPAN class=texhtml><I>n</I> = 3233</SPAN>, <SPAN 
class=texhtml><I>d</I> = 2753</SPAN>). For an encrypted <A 
href="http://en.wikipedia.org/wiki/Ciphertext">ciphertext</A> <SPAN 
class=texhtml><I>c</I></SPAN>, the decryption function is <SPAN 
class=texhtml><I>c</I><SUP>2753</SUP>(mod 3233)</SPAN>.</P>
<P>For instance, in order to encrypt <SPAN class=texhtml><I>m</I> = 65</SPAN>, 
we calculate</P>
<DL>
  <DD><SPAN class=texhtml><I>c</I> = 65<SUP>17</SUP>(mod 3233) = 2790</SPAN>. 
  </DD></DL>
<P>To decrypt <SPAN class=texhtml><I>c</I> = 2790</SPAN>, we calculate</P>
<DL>
  <DD><SPAN class=texhtml><I>m</I> = 2790<SUP>2753</SUP>(mod 3233) = 65</SPAN>. 
  </DD></DL>
<P>Both of these calculations can be computed efficiently using the <A 
class=mw-redirect title="Square-and-multiply algorithm" 
href="http://en.wikipedia.org/wiki/Square-and-multiply_algorithm">square-and-multiply 
algorithm</A> for <A 
href="http://en.wikipedia.org/wiki/Modular_exponentiation">modular 
exponentiation</A>. In real life situations the primes selected would be much 
larger; in our example it would be relatively trivial to factor <SPAN 
class=texhtml><I>n</I></SPAN>, 3233, obtained from the freely available public 
key back to the primes <SPAN class=texhtml><I>p</I></SPAN> and <SPAN 
class=texhtml><I>q</I></SPAN>. Given <SPAN class=texhtml><I>e</I></SPAN>, also 
from the public key, we could then compute <SPAN class=texhtml><I>d</I></SPAN> 
and so acquire the private key.</P>
<H3><SPAN class=editsection>[<A 
title="Edit section: Using the Chinese remainder algorithm" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=7">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Using_the_Chinese_remainder_algorithm>Using the 
Chinese remainder algorithm</SPAN></H3>
<P>For efficiency many popular crypto libraries (like OpenSSL, Java and .NET) 
use the following optimization for decryption and signing: The following values 
are precomputed and stored as part of the private key:</P>
<UL>
  <LI><SPAN class=texhtml><I>p</I></SPAN> and <SPAN 
  class=texhtml><I>q</I></SPAN>: the primes from the key generation, 
  <LI><IMG class=tex alt="d_P = d\mod (p - 1)" 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht14A(1).tmp">, 

  <LI><IMG class=tex alt="d_Q = d\mod(q - 1)" 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht14D(1).tmp"> 
  and 
  <LI><IMG class=tex alt="q_{Inv} = q^{-1} \mod(p)" 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht150(1).tmp">. 
  </LI></UL>
<P>These values allow to compute the exponentiation <IMG class=tex 
alt="m = c^d \mod pq" 
src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht153(1).tmp"> 
more efficiently as follows:</P>
<UL>
  <LI><IMG class=tex alt="m_1 = c^{d_P} \mod p" 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht156(1).tmp"> 

  <LI><IMG class=tex alt="m_2 = c^{d_Q} \mod q" 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht159(1).tmp"> 

  <LI><IMG class=tex alt="h = q_{Inv}*(m_1-m_2) \mod p" 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht15C(1).tmp"> 
  (if <SPAN class=texhtml><I>m</I><SUB>1</SUB> &lt; <I>m</I><SUB>2</SUB></SPAN> 
  then some libraries compute h as <IMG class=tex 
  alt="q_{Inv}*(m_1+p-m_2) \mod p" 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht15F(1).tmp">) 

  <LI><IMG class=tex alt="m = m_2 + h*q\," 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht162(1).tmp"> 
  </LI></UL>
<P>This is more efficient than computing <IMG class=tex alt="m = c^d \mod pq" 
src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht153(1).tmp"> 
even though two modular exponentiations have to be computed. The reason is that 
these two modular exponentiations both use a smaller exponent and a smaller 
modulus.</P>
<H3><SPAN class=editsection>[<A title="Edit section: Attacks against plain RSA" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=8">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Attacks_against_plain_RSA>Attacks against plain 
RSA</SPAN></H3>
<P>There are a number of attacks against plain RSA as described below.</P>
<UL>
  <LI>When encrypting with low encryption exponents (e.g., <SPAN 
  class=texhtml><I>e</I> = 3</SPAN>) and small values of the <SPAN 
  class=texhtml><I>m</I></SPAN>, (i.e. <SPAN class=texhtml><I>m</I> &lt; 
  <I>n</I><SUP>1 / <I>e</I></SUP></SPAN>) the result of <SPAN 
  class=texhtml><I>m</I><SUP><I>e</I></SUP></SPAN> is strictly less than the 
  modulus <SPAN class=texhtml><I>n</I></SPAN>. In this case, ciphertexts can be 
  easily decrypted by taking the <SPAN class=texhtml><I>e</I></SPAN>th root of 
  the ciphertext over the integers. 
  <LI>If the same clear text message is sent to <SPAN 
  class=texhtml><I>e</I></SPAN> or more recipients in an encrypted way, and the 
  receivers share the same exponent <SPAN class=texhtml><I>e</I></SPAN>, but 
  different <SPAN class=texhtml><I>p</I></SPAN>, <SPAN 
  class=texhtml><I>q</I></SPAN>, and <SPAN class=texhtml><I>n</I></SPAN>, then 
  it is easy to decrypt the original clear text message via the <A 
  href="http://en.wikipedia.org/wiki/Chinese_remainder_theorem">Chinese 
  remainder theorem</A>. <A 
  href="http://en.wikipedia.org/wiki/Johan_Håstad">Johan Håstad</A> noticed that 
  this attack is possible even if the cleartexts are not equal, but the attacker 
  knows a linear relation between them.<SUP class=reference id=cite_ref-4><A 
  href="http://en.wikipedia.org/wiki/RSA#cite_note-4"><SPAN>[</SPAN>5<SPAN>]</SPAN></A></SUP> 
  This attack was later improved by <A 
  href="http://en.wikipedia.org/wiki/Don_Coppersmith">Don Coppersmith</A>.<SUP 
  class=reference id=cite_ref-5><A 
  href="http://en.wikipedia.org/wiki/RSA#cite_note-5"><SPAN>[</SPAN>6<SPAN>]</SPAN></A></SUP> 

  <LI>Because RSA encryption is a <A title="Deterministic algorithm" 
  href="http://en.wikipedia.org/wiki/Deterministic_algorithm">deterministic 
  encryption algorithm</A> – i.e., has no random component – an attacker can 
  successfully launch a <A class=mw-redirect title="Chosen plaintext attack" 
  href="http://en.wikipedia.org/wiki/Chosen_plaintext_attack">chosen plaintext 
  attack</A> against the cryptosystem, by encrypting likely plaintexts under the 
  public key and test if they are equal to the ciphertext. A cryptosystem is 
  called <A class=mw-redirect title="Semantically secure" 
  href="http://en.wikipedia.org/wiki/Semantically_secure">semantically 
  secure</A> if an attacker cannot distinguish two encryptions from each other 
  even if the attacker knows (or has chosen) the corresponding plaintexts. As 
  described above, RSA without padding is not semantically secure. 
  <LI>RSA has the property that the product of two ciphertexts is equal to the 
  encryption of the product of the respective plaintexts. That is <IMG class=tex 
  alt="m_1^em_2^e\equiv (m_1m_2)^e\pmod{n}." 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht165(1).tmp"> 
  Because of this multiplicative property a <A 
  href="http://en.wikipedia.org/wiki/Chosen-ciphertext_attack">chosen-ciphertext 
  attack</A> is possible. E.g. an attacker, who wants to know the decryption of 
  a ciphertext <SPAN class=texhtml><I>c</I> = <I>m</I><SUP><I>e</I></SUP>(mod 
  <I>n</I>)</SPAN> may ask the holder of the private key to decrypt an 
  unsuspicious-looking ciphertext <SPAN class=texhtml><I>c</I>' = 
  <I>c</I><I>r</I><SUP><I>e</I></SUP>(mod <I>n</I>)</SPAN> for some value <SPAN 
  class=texhtml><I>r</I></SPAN> chosen by the attacker. Because of the 
  multiplicative property <SPAN class=texhtml><I>c</I>'</SPAN> is the encryption 
  of <SPAN class=texhtml><I>m</I><I>r</I>(mod <I>n</I>)</SPAN>. Hence, if the 
  attacker is successful with the attack, he will learn <SPAN 
  class=texhtml><I>m</I><I>r</I>(mod <I>n</I>)</SPAN> from which he can derive 
  the message <I>m</I> by multiplying <SPAN 
  class=texhtml><I>m</I><I>r</I></SPAN> with the modular inverse of <SPAN 
  class=texhtml><I>r</I></SPAN> modulo <SPAN class=texhtml><I>n</I></SPAN>. 
</LI></UL>
<H3><SPAN class=editsection>[<A title="Edit section: Padding schemes" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=9">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Padding_schemes>Padding schemes</SPAN></H3>
<P>To avoid these problems, practical RSA implementations typically embed some 
form of structured, randomized <A title="Padding (cryptography)" 
href="http://en.wikipedia.org/wiki/Padding_(cryptography)">padding</A> into the 
value <SPAN class=texhtml><I>m</I></SPAN> before encrypting it. This padding 
ensures that <SPAN class=texhtml><I>m</I></SPAN> does not fall into the range of 
insecure plaintexts, and that a given message, once padded, will encrypt to one 
of a large number of different possible ciphertexts.</P>
<P>Standards such as <A title=PKCS1 
href="http://en.wikipedia.org/wiki/PKCS1">PKCS#1</A> have been carefully 
designed to securely pad messages prior to RSA encryption. Because these schemes 
pad the plaintext <SPAN class=texhtml><I>m</I></SPAN> with some number of 
additional bits, the size of the un-padded message <B>M</B> must be somewhat 
smaller. RSA padding schemes must be carefully designed so as to prevent 
sophisticated attacks which may be facilitated by a predictable message 
structure. Early versions of the PKCS#1 standard (up to version 1.5) used a 
construction that turned RSA into a semantically secure encryption scheme. This 
version was later found vulnerable to a practical <A class=mw-redirect 
title="Adaptive chosen ciphertext attack" 
href="http://en.wikipedia.org/wiki/Adaptive_chosen_ciphertext_attack">adaptive 
chosen ciphertext attack</A>. Later versions of the standard include <A 
class=mw-redirect title="Optimal Asymmetric Encryption Padding" 
href="http://en.wikipedia.org/wiki/Optimal_Asymmetric_Encryption_Padding">Optimal 
Asymmetric Encryption Padding</A> (OAEP), which prevents these attacks. The 
PKCS#1 standard also incorporates processing schemes designed to provide 
additional security for RSA signatures, e.g., the Probabilistic Signature Scheme 
for RSA (<A class=mw-redirect title=RSA-PSS 
href="http://en.wikipedia.org/wiki/RSA-PSS">RSA-PSS</A>).</P>
<P>In the common case where RSA is used to exchange symmetric keys, <A 
href="http://en.wikipedia.org/wiki/Key_encapsulation">key encapsulation</A> 
provides a simpler alternative to padding. Instead of generating a random 
symmetric key, padding it and then encrypting the padded version with RSA, a 
random integer <I>m</I> between 1 and <I>n</I>-1 is generated and encrypted 
directly using RSA. Both the sender and receiver generate identical symmetric 
keys by applying the same <A 
href="http://en.wikipedia.org/wiki/Key_derivation_function">key derivation 
function</A> to <I>m.</I><SUP class=reference id=cite_ref-6><A 
href="http://en.wikipedia.org/wiki/RSA#cite_note-6"><SPAN>[</SPAN>7<SPAN>]</SPAN></A></SUP></P>
<H3><SPAN class=editsection>[<A title="Edit section: Signing messages" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=10">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Signing_messages>Signing messages</SPAN></H3>
<P>Suppose <A title="Alice and Bob" 
href="http://en.wikipedia.org/wiki/Alice_and_Bob">Alice</A> uses <A 
title="Alice and Bob" 
href="http://en.wikipedia.org/wiki/Alice_and_Bob">Bob</A>'s public key to send 
him an encrypted message. In the message, she can claim to be Alice but Bob has 
no way of verifying that the message was actually from Alice since anyone can 
use Bob's public key to send him encrypted messages. In order to verify the 
origin of a message, RSA can also be used to <A title="Digital signature" 
href="http://en.wikipedia.org/wiki/Digital_signature">sign</A> a message.</P>
<P>Suppose Alice wishes to send a signed message to Bob. She can use her own 
private key to do so. She produces a <A title="Cryptographic hash function" 
href="http://en.wikipedia.org/wiki/Cryptographic_hash_function">hash value</A> 
of the message, raises it to the power of <SPAN class=texhtml><I>d</I>mod 
<I>n</I></SPAN> (as she does when decrypting a message), and attaches it as a 
"signature" to the message. When Bob receives the signed message, he uses the 
same hash algorithm in conjunction with Alice's public key. He raises the 
signature to the power of <SPAN class=texhtml><I>e</I>mod <I>n</I></SPAN> (as he 
does when encrypting a message), and compares the resulting hash value with the 
message's actual hash value. If the two agree, he knows that the author of the 
message was in possession of Alice's private key, and that the message has not 
been tampered with since.</P>
<P>Secure padding schemes such as <A class=mw-redirect title=RSA-PSS 
href="http://en.wikipedia.org/wiki/RSA-PSS">RSA-PSS</A> are as essential for the 
security of message signing as they are for message encryption. The same key 
should never be used for both encryption and signing.<SUP class=reference 
id=cite_ref-7><A 
href="http://en.wikipedia.org/wiki/RSA#cite_note-7"><SPAN>[</SPAN>8<SPAN>]</SPAN></A></SUP></P>
<H2><SPAN class=editsection>[<A 
title="Edit section: Security and practical considerations" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=11">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Security_and_practical_considerations>Security and 
practical considerations</SPAN></H2>
<H3><SPAN class=editsection>[<A 
title="Edit section: Integer factorization and RSA problem" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=12">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Integer_factorization_and_RSA_problem>Integer 
factorization and RSA problem</SPAN></H3>
<DIV class="rellink boilerplate seealso">See also: <A 
href="http://en.wikipedia.org/wiki/RSA_Factoring_Challenge">RSA Factoring 
Challenge</A>&nbsp;and <A 
href="http://en.wikipedia.org/wiki/Integer_factorization_records">Integer 
factorization records</A></DIV>
<P>The security of the RSA cryptosystem is based on two mathematical problems: 
the problem of <A title="Integer factorization" 
href="http://en.wikipedia.org/wiki/Integer_factorization">factoring large 
numbers</A> and the <A href="http://en.wikipedia.org/wiki/RSA_problem">RSA 
problem</A>. Full decryption of an RSA ciphertext is thought to be infeasible on 
the assumption that both of these problems are hard, i.e., no efficient 
algorithm exists for solving them. Providing security against <I>partial</I> 
decryption may require the addition of a secure <A 
title="Padding (cryptography)" 
href="http://en.wikipedia.org/wiki/Padding_(cryptography)">padding 
scheme</A>.<SUP class=Template-Fact 
title="This claim needs references to reliable sources from January 2009" 
style="WHITE-SPACE: nowrap">[<I><A title="Wikipedia:Citation needed" 
href="http://en.wikipedia.org/wiki/Wikipedia:Citation_needed">citation 
needed</A></I>]</SUP></P>
<P>The <A href="http://en.wikipedia.org/wiki/RSA_problem">RSA problem</A> is 
defined as the task of taking <SPAN class=texhtml><I>e</I></SPAN>th roots modulo 
a composite <SPAN class=texhtml><I>n</I></SPAN>: recovering a value <SPAN 
class=texhtml><I>m</I></SPAN> such that <SPAN class=texhtml><I>c</I> = 
<I>m</I><SUP><I>e</I></SUP>mod <I>n</I></SPAN>, where <SPAN 
class=texhtml>(<I>n</I>,<I>e</I>)</SPAN> is an RSA public key and <SPAN 
class=texhtml><I>c</I></SPAN> is an RSA ciphertext. Currently the most promising 
approach to solving the RSA problem is to factor the modulus <SPAN 
class=texhtml><I>n</I></SPAN>. With the ability to recover prime factors, an 
attacker can compute the secret exponent <SPAN class=texhtml><I>d</I></SPAN> 
from a public key <SPAN class=texhtml>(<I>n</I>,<I>e</I>)</SPAN>, then decrypt 
<SPAN class=texhtml><I>c</I></SPAN> using the standard procedure. To accomplish 
this, an attacker factors <SPAN class=texhtml><I>n</I></SPAN> into <SPAN 
class=texhtml><I>p</I></SPAN> and <SPAN class=texhtml><I>q</I></SPAN>, and 
computes <SPAN class=texhtml>(<I>p</I> − 1)(<I>q</I> − 1)</SPAN> which allows 
the determination of <SPAN class=texhtml><I>d</I></SPAN> from <SPAN 
class=texhtml><I>e</I></SPAN>. No polynomial-time method for factoring large 
integers on a classical computer has yet been found, but it has not been proven 
that none exists. See <A 
href="http://en.wikipedia.org/wiki/Integer_factorization">integer 
factorization</A> for a discussion of this problem. Rivest, Shamir and Adleman 
have shown that finding <I>d</I> from <I>n</I> and <I>e</I> is equally hard as 
factoring <I>n</I> into <I>p</I> and <I>q</I><SUP class=reference 
id=cite_ref-rsa_0-1><A 
href="http://en.wikipedia.org/wiki/RSA#cite_note-rsa-0"><SPAN>[</SPAN>1<SPAN>]</SPAN></A></SUP>. 
However, this proof does not imply that inverting RSA is equally hard as 
factoring.</P>
<P>As of 2010<SUP class="plainlinks noprint asof-tag update" 
style="DISPLAY: none"><A class="external text" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit" 
rel=nofollow>[update]</A></SUP>, the largest (known) number factored by a <A 
title="General number field sieve" 
href="http://en.wikipedia.org/wiki/General_number_field_sieve">general-purpose 
factoring</A> algorithm was 768 bits long (see <A class=mw-redirect 
title=RSA-768 href="http://en.wikipedia.org/wiki/RSA-768">RSA-768</A>), using a 
state-of-the-art distributed implementation. RSA keys are typically 1024–2048 
bits long. Some experts believe that 1024-bit keys may become breakable in the 
near term (though this is disputed); few see any way that 4096-bit keys could be 
broken in the foreseeable future. Therefore, it is generally presumed that RSA 
is secure if <SPAN class=texhtml><I>n</I></SPAN> is sufficiently large. If <SPAN 
class=texhtml><I>n</I></SPAN> is 300 <A title=Bit 
href="http://en.wikipedia.org/wiki/Bit">bits</A> or shorter, it can be factored 
in a few hours on a <A 
href="http://en.wikipedia.org/wiki/Personal_computer">personal computer</A>, 
using software already freely available. Keys of 512 bits have been shown to be 
practically breakable in 1999 when <A class=mw-redirect title=RSA-155 
href="http://en.wikipedia.org/wiki/RSA-155">RSA-155</A> was factored by using 
several hundred computers and are now factored in a few weeks using common 
hardware.<SUP class=reference id=cite_ref-8><A 
href="http://en.wikipedia.org/wiki/RSA#cite_note-8"><SPAN>[</SPAN>9<SPAN>]</SPAN></A></SUP> 
A theoretical hardware device named <A 
href="http://en.wikipedia.org/wiki/TWIRL">TWIRL</A> and described by Shamir and 
Tromer in 2003 called into question the security of 1024 bit keys. It is 
currently recommended that <SPAN class=texhtml><I>n</I></SPAN> be at least 2048 
bits long.<SUP class=reference id=cite_ref-9><A 
href="http://en.wikipedia.org/wiki/RSA#cite_note-9"><SPAN>[</SPAN>10<SPAN>]</SPAN></A></SUP></P>
<P>In 1994, <A href="http://en.wikipedia.org/wiki/Peter_Shor">Peter Shor</A> 
showed that a <A href="http://en.wikipedia.org/wiki/Quantum_computer">quantum 
computer</A> (if one could ever be practically created for the purpose) would be 
able to factor in <A class=mw-redirect title="Polynomial time" 
href="http://en.wikipedia.org/wiki/Polynomial_time">polynomial time</A>, 
breaking RSA.</P>
<H3><SPAN class=editsection>[<A title="Edit section: Key generation" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=13">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Key_generation_2>Key generation</SPAN></H3>
<P>Finding the large primes <I>p</I> and <I>q</I> is usually done by testing 
random numbers of the right size with probabilistic <A title="Primality test" 
href="http://en.wikipedia.org/wiki/Primality_test">primality tests</A> which 
quickly eliminate virtually all non-primes.</P>
<P>Numbers <I>p</I> and <I>q</I> should not be 'too close', lest the <A 
class=mw-redirect title="Fermat factorization" 
href="http://en.wikipedia.org/wiki/Fermat_factorization">Fermat 
factorization</A> for <I>n</I> be successful, if <I>p</I>&nbsp;−&nbsp;<I>q</I>, 
for instance is less than 2<I>n</I><SUP>1/4</SUP> (which for even small 1024-bit 
values of <I>n</I> is 3×10<SUP>77</SUP>) solving for <I>p</I> and <I>q</I> is 
trivial. Furthermore, if either <I>p</I>&nbsp;−&nbsp;1 or <I>q</I>&nbsp;−&nbsp;1 
has only small prime factors, <I>n</I> can be factored quickly by <A 
title="Pollard's p − 1 algorithm" 
href="http://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm">Pollard's 
<I>p</I>&nbsp;−&nbsp;1 algorithm</A>, and these values of <I>p</I> or <I>q</I> 
should therefore be discarded as well.</P>
<P>It is important that the private key <I>d</I> be large enough. <A class=new 
title="Michael J. Wiener (page does not exist)" 
href="http://en.wikipedia.org/w/index.php?title=Michael_J._Wiener&amp;action=edit&amp;redlink=1">Michael 
J. Wiener</A> showed<SUP class=reference id=cite_ref-wiener_10-0><A 
href="http://en.wikipedia.org/wiki/RSA#cite_note-wiener-10"><SPAN>[</SPAN>11<SPAN>]</SPAN></A></SUP> 
that if <I>p</I> is between <I>q</I> and 2<I>q</I> (which is quite typical) and 
<I>d</I>&nbsp;&lt;&nbsp;<I>n</I><SUP>1/4</SUP>/3, then <I>d</I> can be computed 
efficiently from <I>n</I> and&nbsp;<I>e</I>. There is no known attack against 
small public exponents such as <I>e</I>&nbsp;=&nbsp;3, provided that proper 
padding is used. However, when no padding is used, or when the padding is 
improperly implemented, small public exponents have a greater risk of leading to 
an attack, such as the unpadded plaintext vulnerability listed above. <A 
class=mw-redirect title=65537 
href="http://en.wikipedia.org/wiki/65537">65537</A> is a commonly used value 
for&nbsp;<I>e</I>. This value can be regarded as a compromise between avoiding 
potential small exponent attacks and still allowing efficient encryptions (or 
signature verification). The NIST Special Publication on Computer Security (SP 
800-78 Rev 1 of August 2007) does not allow public exponents <I>e</I> smaller 
than 65537, but does not state a reason for this restriction.</P>
<P><BR></P>
<P>This procedure raises additional security issues. For instance, it is of 
utmost importance to use a strong <A class=mw-redirect 
title="Random number generator" 
href="http://en.wikipedia.org/wiki/Random_number_generator">random number 
generator</A> for the symmetric key, because otherwise Eve (an eavesdropper 
wanting to see what was sent) could bypass RSA by guessing the symmetric 
key.</P>
<H3><SPAN class=editsection>[<A title="Edit section: Timing attacks" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=14">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Timing_attacks>Timing attacks</SPAN></H3>
<P><A title="Paul Kocher" 
href="http://en.wikipedia.org/wiki/Paul_Kocher">Kocher</A> described a new 
attack on RSA in 1995: if the attacker Eve knows Alice's hardware in sufficient 
detail and is able to measure the decryption times for several known 
ciphertexts, she can deduce the decryption key <SPAN 
class=texhtml><I>d</I></SPAN> quickly. This attack can also be applied against 
the RSA signature scheme. In 2003, <A title="Dan Boneh" 
href="http://en.wikipedia.org/wiki/Dan_Boneh">Boneh</A> and <A 
title="David Brumley" 
href="http://en.wikipedia.org/wiki/David_Brumley">Brumley</A> demonstrated a 
more practical attack capable of recovering RSA factorizations over a network 
connection (e.g., from a <A class=mw-redirect title="Secure Socket Layer" 
href="http://en.wikipedia.org/wiki/Secure_Socket_Layer">Secure Socket Layer</A> 
(SSL)-enabled webserver). This attack takes advantage of information leaked by 
the <A href="http://en.wikipedia.org/wiki/Chinese_remainder_theorem">Chinese 
remainder theorem</A> optimization used by many RSA implementations.</P>
<P>One way to thwart these attacks is to ensure that the decryption operation 
takes a constant amount of time for every ciphertext. However, this approach can 
significantly reduce performance. Instead, most RSA implementations use an 
alternate technique known as <A title="Blinding (cryptography)" 
href="http://en.wikipedia.org/wiki/Blinding_(cryptography)">cryptographic 
blinding</A>. RSA blinding makes use of the multiplicative property of RSA. 
Instead of computing <SPAN class=texhtml><I>c</I><SUP><I>d</I></SUP>mod 
<I>n</I></SPAN>, Alice first chooses a secret random value <SPAN 
class=texhtml><I>r</I></SPAN> and computes <SPAN 
class=texhtml>(<I>r</I><SUP><I>e</I></SUP><I>c</I>)<SUP><I>d</I></SUP>mod 
<I>n</I></SPAN>. The result of this computation after applying <A 
class=mw-redirect title="Euler's Theorem" 
href="http://en.wikipedia.org/wiki/Euler's_Theorem">Euler's Theorem</A> is <IMG 
class=tex alt="r c^d ~ \bmod ~n" 
src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht168(1).tmp"> 
and so the effect of <SPAN class=texhtml><I>r</I></SPAN> can be removed by 
multiplying by its inverse. A new value of <SPAN class=texhtml><I>r</I></SPAN> 
is chosen for each ciphertext. With blinding applied, the decryption time is no 
longer correlated to the value of the input ciphertext and so the timing attack 
fails.</P>
<H3><SPAN class=editsection>[<A 
title="Edit section: Adaptive chosen ciphertext attacks" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=15">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Adaptive_chosen_ciphertext_attacks>Adaptive chosen 
ciphertext attacks</SPAN></H3>
<P>In 1998, <A href="http://en.wikipedia.org/wiki/Daniel_Bleichenbacher">Daniel 
Bleichenbacher</A> described the first practical <A class=mw-redirect 
title="Adaptive chosen ciphertext attack" 
href="http://en.wikipedia.org/wiki/Adaptive_chosen_ciphertext_attack">adaptive 
chosen ciphertext attack</A>, against RSA-encrypted messages using the PKCS #1 
v1 <A title="Padding (cryptography)" 
href="http://en.wikipedia.org/wiki/Padding_(cryptography)">padding scheme</A> (a 
padding scheme randomizes and adds structure to an RSA-encrypted message, so it 
is possible to determine whether a decrypted message is valid.) Due to flaws 
with the PKCS #1 scheme, Bleichenbacher was able to mount a practical attack 
against RSA implementations of the <A class=mw-redirect 
title="Secure Socket Layer" 
href="http://en.wikipedia.org/wiki/Secure_Socket_Layer">Secure Socket Layer</A> 
protocol, and to recover session keys. As a result of this work, cryptographers 
now recommend the use of provably secure padding schemes such as <A 
class=mw-redirect title="Optimal Asymmetric Encryption Padding" 
href="http://en.wikipedia.org/wiki/Optimal_Asymmetric_Encryption_Padding">Optimal 
Asymmetric Encryption Padding</A>, and RSA Laboratories has released new 
versions of PKCS #1 that are not vulnerable to these attacks.</P>
<H3><SPAN class=editsection>[<A 
title="Edit section: Side-channel analysis attacks" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=16">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Side-channel_analysis_attacks>Side-channel analysis 
attacks</SPAN></H3>
<P>A side-channel attack using branch prediction analysis (BPA) has been 
described. Many processors use a <A 
href="http://en.wikipedia.org/wiki/Branch_predictor">branch predictor</A> to 
determine whether a conditional branch in the instruction flow of a program is 
likely to be taken or not. Often these processors also implement <A 
href="http://en.wikipedia.org/wiki/Simultaneous_multithreading">simultaneous 
multithreading</A> (SMT). Branch prediction analysis attacks use a spy process 
to discover (statistically) the private key when processed with these 
processors.</P>
<P>Simple Branch Prediction Analysis (SBPA) claims to improve BPA in a 
non-statistical way. In their paper, "On the Power of Simple Branch Prediction 
Analysis"<SUP class=reference id=cite_ref-11><A 
href="http://en.wikipedia.org/wiki/RSA#cite_note-11"><SPAN>[</SPAN>12<SPAN>]</SPAN></A></SUP>, 
the authors of SBPA (<A class=new title="Onur Aciicmez (page does not exist)" 
href="http://en.wikipedia.org/w/index.php?title=Onur_Aciicmez&amp;action=edit&amp;redlink=1">Onur 
Aciicmez</A> and <A class=new title="Cetin Kaya Koc (page does not exist)" 
href="http://en.wikipedia.org/w/index.php?title=Cetin_Kaya_Koc&amp;action=edit&amp;redlink=1">Cetin 
Kaya Koc</A>) claim to have discovered 508 out of 512 bits of an RSA key in 10 
iterations.</P>
<P>A power fault attack on RSA implementations has been described in 2010<SUP 
class=reference id=cite_ref-12><A 
href="http://en.wikipedia.org/wiki/RSA#cite_note-12"><SPAN>[</SPAN>13<SPAN>]</SPAN></A></SUP>.</P>
<H2><SPAN class=editsection>[<A title="Edit section: Proofs of correctness" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=17">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Proofs_of_correctness>Proofs of 
correctness</SPAN></H2>
<H3><SPAN class=editsection>[<A 
title="Edit section: Concise proof using Euler's Theorem" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=18">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Concise_proof_using_Euler.27s_Theorem>Concise proof 
using Euler's Theorem</SPAN></H3>
<P>To show that a message encrypted with <I>e</I> can be decrypted with <I>d</I> 
we need to prove</P>
<DL>
  <DD><IMG class=tex alt="m \equiv (m^e)^d ~ \pmod{n}" 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht16B(1).tmp"> 
  </DD></DL>
<P>i.e.</P>
<DL>
  <DD><IMG class=tex alt="m \equiv m^{ed}\pmod{n}." 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht16E(1).tmp"> 
  </DD></DL>
<P>Now, since <IMG class=tex alt="ed = 1 + k\varphi(n)" 
src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht171(1).tmp">,</P>
<DL>
  <DD><IMG class=tex 
  alt="m^{ed} \equiv m^{1 + k\varphi(n)} \equiv m (m^{\varphi(n)})^{k} \equiv m \pmod{n}." 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht174(1).tmp"> 
  </DD></DL>
<P>The last congruence directly follows from <A 
href="http://en.wikipedia.org/wiki/Euler's_theorem">Euler's theorem</A> when 
<SPAN class=texhtml><I>m</I></SPAN> is relatively prime to <SPAN 
class=texhtml><I>n</I></SPAN>.</P>
<H3><SPAN class=editsection>[<A 
title="Edit section: Proof using Fermat's Little Theorem and Chinese Remainder Theorem" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=19">edit</A>]</SPAN> 
<SPAN class=mw-headline 
id=Proof_using_Fermat.27s_Little_Theorem_and_Chinese_Remainder_Theorem>Proof 
using Fermat's Little Theorem and Chinese Remainder Theorem</SPAN></H3>
<P>Another way to prove the correctness of RSA is based on <A 
href="http://en.wikipedia.org/wiki/Fermat's_little_theorem">Fermat's little 
theorem</A>. This theorem states that if <I>p</I> is prime and <I>p</I> does not 
divide <I>a</I> then</P>
<DL>
  <DD><IMG class=tex alt=" a^{(p-1)} \equiv 1 \pmod{p}." 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht177(1).tmp"> 
  </DD></DL>
<P>In RSA, the modulus <SPAN class=texhtml><I>n</I> = <I>p</I><I>q</I></SPAN> is 
a product of two primes <I>p</I> and <I>q</I>. The public key <I>e</I> and 
private key <I>d</I> satisfy</P>
<DL>
  <DD><IMG class=tex alt="e d \equiv 1\pmod{(p-1)(q-1)}." 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht17A(1).tmp"> 
  </DD></DL>
<P>Therefore, there exists an integer <I>h</I>, such that</P>
<DL>
  <DD><SPAN class=texhtml><I>e</I><I>d</I> − 1 = <I>h</I>(<I>p</I> − 1)(<I>q</I> 
  − 1).</SPAN> </DD></DL>
<P>We can then continue to calculate</P>
<DL>
  <DD><IMG class=tex 
  alt="\left(m^e\right)^d \equiv m^{e d} \equiv m^{(e d - 1)}m \equiv m^{h(p-1)(q-1)}m \equiv 1^{h(q-1)}m\equiv m \pmod{p}." 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht17D(1).tmp"> 
  </DD></DL>
<P>And likewise for <I>q</I></P>
<DL>
  <DD><IMG class=tex 
  alt="\left(m^e\right)^d \equiv m^{e d} \equiv m^{(e d - 1)}m \equiv m^{h(p-1)(q-1)}m \equiv 1^{h(p-1)}m\equiv m \pmod{q}." 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht180(1).tmp"> 
  </DD></DL>
<P>If <I>p</I> and <I>q</I> are coprime, <IMG class=tex alt="a\equiv b \pmod{p}" 
src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht183(1).tmp"> 
and <IMG class=tex alt="a\equiv b \pmod{q}" 
src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht186(1).tmp"> 
then the <A 
href="http://en.wikipedia.org/wiki/Chinese_remainder_theorem">Chinese remainder 
theorem</A> implies <IMG class=tex alt="a\equiv b \pmod{pq}" 
src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht189(1).tmp">. 
Hence</P>
<DL>
  <DD><IMG class=tex alt="\left(m^e\right)^d \equiv m \pmod{pq}." 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht18C(1).tmp"> 
  </DD></DL>
<H2><SPAN class=editsection>[<A title="Edit section: See also" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=20">edit</A>]</SPAN> 
<SPAN class=mw-headline id=See_also>See also</SPAN></H2>
<UL>
  <LI><A href="http://en.wikipedia.org/wiki/Public-key_cryptography">Public-key 
  cryptography</A> 
  <LI><A href="http://en.wikipedia.org/wiki/Encryption">Encryption</A> 
  <LI><A href="http://en.wikipedia.org/wiki/Key_exchange">Key exchange</A> 
  <LI><A class=mw-redirect title="Diffie-Hellman key exchange" 
  href="http://en.wikipedia.org/wiki/Diffie-Hellman_key_exchange">Diffie-Hellman 
  key exchange</A> 
  <LI><A href="http://en.wikipedia.org/wiki/Key_management">Key management</A> 
  <LI><A class=mw-redirect title="Cryptographic key length" 
  href="http://en.wikipedia.org/wiki/Cryptographic_key_length">Cryptographic key 
  length</A> 
  <LI><A 
  href="http://en.wikipedia.org/wiki/Computational_complexity_theory">Computational 
  complexity theory</A> </LI></UL>
<H2><SPAN class=editsection>[<A title="Edit section: Notes" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=21">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Notes>Notes</SPAN></H2>
<DIV class=reflist>
<DIV class=references>
<OL>
  <LI id=cite_note-rsa-0>^ <A 
  href="http://en.wikipedia.org/wiki/RSA#cite_ref-rsa_0-0"><SUP><I><B>a</B></I></SUP></A> 
  <A 
  href="http://en.wikipedia.org/wiki/RSA#cite_ref-rsa_0-1"><SUP><I><B>b</B></I></SUP></A> 
  <SPAN class="citation Journal">Rivest, R.; A. Shamir; L. Adleman (1978). <A 
  class="external text" href="http://theory.lcs.mit.edu/~rivest/rsapaper.pdf" 
  rel=nofollow>"A Method for Obtaining Digital Signatures and Public-Key 
  Cryptosystems"</A>. <I>Communications of the ACM</I> <B>21</B> (2): 120–126. 
  <A title="Digital object identifier" 
  href="http://en.wikipedia.org/wiki/Digital_object_identifier">doi</A>:<A 
  class="external text" href="http://dx.doi.org/10.1145/359340.359342" 
  rel=nofollow>10.1145/359340.359342</A><SPAN class=printonly>. <A 
  class="external free" href="http://theory.lcs.mit.edu/~rivest/rsapaper.pdf" 
  rel=nofollow>http://theory.lcs.mit.edu/~rivest/rsapaper.pdf</A></SPAN>.</SPAN><SPAN 
  class=Z3988 
  title=ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&amp;rft.genre=article&amp;rft.atitle=A+Method+for+Obtaining+Digital+Signatures+and+Public-Key+Cryptosystems&amp;rft.jtitle=Communications+of+the+ACM&amp;rft.aulast=Rivest&amp;rft.aufirst=R.&amp;rft.au=Rivest%2C%26%2332%3BR.&amp;rft.date=1978&amp;rft.volume=21&amp;rft.issue=2&amp;rft.pages=120%E2%80%93126&amp;rft_id=info:doi/10.1145%2F359340.359342&amp;rft_id=http%3A%2F%2Ftheory.lcs.mit.edu%2F%7Erivest%2Frsapaper.pdf&amp;rfr_id=info:sid/en.wikipedia.org:RSA><SPAN 
  style="DISPLAY: none">&nbsp;</SPAN></SPAN> 
  <LI id=cite_note-SIAM-1>^ <A 
  href="http://en.wikipedia.org/wiki/RSA#cite_ref-SIAM_1-0"><SUP><I><B>a</B></I></SUP></A> 
  <A 
  href="http://en.wikipedia.org/wiki/RSA#cite_ref-SIAM_1-1"><SUP><I><B>b</B></I></SUP></A> 
  <A class="external text" 
  href="http://www.msri.org/people/members/sara/articles/rsa.pdf" 
  rel=nofollow>SIAM News, Volume 36, Number 5, June 2003</A>, "Still Guarding 
  Secrets after Years of Attacks, RSA Earns Accolades for its Founders", by Sara 
  Robinson 
  <LI id=cite_note-2><B><A 
  href="http://en.wikipedia.org/wiki/RSA#cite_ref-2">^</A></B> <A 
  class="external free" href="http://www.rsa.com/press_release.aspx?id=261" 
  rel=nofollow>http://www.rsa.com/press_release.aspx?id=261</A> 
  <LI id=cite_note-Boneh-3><B><A 
  href="http://en.wikipedia.org/wiki/RSA#cite_ref-Boneh_3-0">^</A></B> <SPAN 
  class="citation Journal">Boneh, Dan (1999). <A class="external text" 
  href="http://crypto.stanford.edu/~dabo/abstracts/RSAattack-survey.html" 
  rel=nofollow>"Twenty Years of attacks on the RSA Cryptosystem"</A>. <I>Notices 
  of the American Mathematical Society (AMS)</I> <B>46</B> (2): 203–213<SPAN 
  class=printonly>. <A class="external free" 
  href="http://crypto.stanford.edu/~dabo/abstracts/RSAattack-survey.html" 
  rel=nofollow>http://crypto.stanford.edu/~dabo/abstracts/RSAattack-survey.html</A></SPAN>.</SPAN><SPAN 
  class=Z3988 
  title=ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&amp;rft.genre=article&amp;rft.atitle=Twenty+Years+of+attacks+on+the+RSA+Cryptosystem&amp;rft.jtitle=Notices+of+the+American+Mathematical+Society+%28AMS%29&amp;rft.aulast=Boneh&amp;rft.aufirst=Dan&amp;rft.au=Boneh%2C%26%2332%3BDan&amp;rft.date=1999&amp;rft.volume=46&amp;rft.issue=2&amp;rft.pages=203%E2%80%93213&amp;rft_id=http%3A%2F%2Fcrypto.stanford.edu%2F%7Edabo%2Fabstracts%2FRSAattack-survey.html&amp;rfr_id=info:sid/en.wikipedia.org:RSA><SPAN 
  style="DISPLAY: none">&nbsp;</SPAN></SPAN> 
  <LI id=cite_note-4><B><A 
  href="http://en.wikipedia.org/wiki/RSA#cite_ref-4">^</A></B> Johan Håstad, "On 
  using RSA with Low Exponent in a Public Key Network", Crypto 85 
  <LI id=cite_note-5><B><A 
  href="http://en.wikipedia.org/wiki/RSA#cite_ref-5">^</A></B> Don Coppersmith, 
  "Small Solutions to Polynomial Equations, and Low Exponent RSA 
  Vulnerabilities", Journal of Cryptology, v. 10, n. 4, Dec. 1997 
  <LI id=cite_note-6><B><A 
  href="http://en.wikipedia.org/wiki/RSA#cite_ref-6">^</A></B> <A 
  class="external text" 
  href="http://lists.w3.org/Archives/Public/public-xmlsec/2009May/att-0032/Key_Encapsulation.pdf" 
  rel=nofollow>Key Encapsulation: A New Scheme for Public-Key Encryption</A>, 
  XML Security Working Group F2F, May 2009 
  <LI id=cite_note-7><B><A 
  href="http://en.wikipedia.org/wiki/RSA#cite_ref-7">^</A></B> <A 
  class="external free" href="http://www.di-mgt.com.au/rsa_alg.html#weaknesses" 
  rel=nofollow>http://www.di-mgt.com.au/rsa_alg.html#weaknesses</A> 
  <LI id=cite_note-8><B><A 
  href="http://en.wikipedia.org/wiki/RSA#cite_ref-8">^</A></B> <A 
  class="external text" 
  href="http://www.mersenneforum.org/showthread.php?t=9787" rel=nofollow>518-bit 
  GNFS with msieve</A> 
  <LI id=cite_note-9><B><A 
  href="http://en.wikipedia.org/wiki/RSA#cite_ref-9">^</A></B> <A 
  class="external text" href="http://www.rsa.com/rsalabs/node.asp?id=2007" 
  rel=nofollow>Has the RSA algorithm been compromised as a result of Bernstein's 
  Paper?</A> What key size should I be using? 
  <LI id=cite_note-wiener-10><B><A 
  href="http://en.wikipedia.org/wiki/RSA#cite_ref-wiener_10-0">^</A></B> <SPAN 
  class="citation Journal">Wiener, Michael J. (May 1990). "Cryptanalysis of 
  short RSA secret exponents". <I>Information Theory, IEEE Transactions on</I> 
  <B>36</B> (3): 553–558. <A title="Digital object identifier" 
  href="http://en.wikipedia.org/wiki/Digital_object_identifier">doi</A>:<A 
  class="external text" href="http://dx.doi.org/10.1109/18.54902" 
  rel=nofollow>10.1109/18.54902</A>.</SPAN><SPAN class=Z3988 
  title=ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&amp;rft.genre=article&amp;rft.atitle=Cryptanalysis+of+short+RSA+secret+exponents&amp;rft.jtitle=Information+Theory%2C+IEEE+Transactions+on&amp;rft.aulast=Wiener&amp;rft.aufirst=Michael+J.&amp;rft.au=Wiener%2C%26%2332%3BMichael+J.&amp;rft.date=May+1990&amp;rft.volume=36&amp;rft.issue=3&amp;rft.pages=553%E2%80%93558&amp;rft_id=info:doi/10.1109%2F18.54902&amp;rfr_id=info:sid/en.wikipedia.org:RSA><SPAN 
  style="DISPLAY: none">&nbsp;</SPAN></SPAN> 
  <LI id=cite_note-11><B><A 
  href="http://en.wikipedia.org/wiki/RSA#cite_ref-11">^</A></B> <A 
  class="external free" 
  href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80.1438&amp;rep=rep1&amp;type=pdf" 
  rel=nofollow>http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80.1438&amp;rep=rep1&amp;type=pdf</A> 

  <LI id=cite_note-12><B><A 
  href="http://en.wikipedia.org/wiki/RSA#cite_ref-12">^</A></B> <A 
  class="external text" 
  href="http://www.eecs.umich.edu/~valeria/research/publications/DATE10RSA.pdf" 
  rel=nofollow>FaultBased Attack of RSA Authentication</A> </LI></OL></DIV></DIV>
<H2><SPAN class=editsection>[<A title="Edit section: References" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=22">edit</A>]</SPAN> 
<SPAN class=mw-headline id=References>References</SPAN></H2>
<UL>
  <LI><SPAN class="citation book">Menezes, Alfred; Paul C. van Oorschot; Scott 
  A. Vanstone (October 1996). <I>Handbook of Applied Cryptography</I>. CRC 
  Press. <A title="International Standard Book Number" 
  href="http://en.wikipedia.org/wiki/International_Standard_Book_Number">ISBN</A>&nbsp;<A 
  title=Special:BookSources/0-8493-8523-7 
  href="http://en.wikipedia.org/wiki/Special:BookSources/0-8493-8523-7">0-8493-8523-7</A>.</SPAN><SPAN 
  class=Z3988 
  title=ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rft.genre=book&amp;rft.btitle=Handbook+of+Applied+Cryptography&amp;rft.aulast=Menezes&amp;rft.aufirst=Alfred&amp;rft.au=Menezes%2C%26%2332%3BAlfred&amp;rft.date=October+1996&amp;rft.pub=CRC+Press&amp;rft.isbn=0-8493-8523-7&amp;rfr_id=info:sid/en.wikipedia.org:RSA><SPAN 
  style="DISPLAY: none">&nbsp;</SPAN></SPAN> 
  <LI><SPAN class="citation book"><A title="Thomas H. Cormen" 
  href="http://en.wikipedia.org/wiki/Thomas_H._Cormen">Cormen, Thomas H.</A>; <A 
  href="http://en.wikipedia.org/wiki/Charles_E._Leiserson">Charles E. 
  Leiserson</A>; <A class=mw-redirect title="Ronald L. Rivest" 
  href="http://en.wikipedia.org/wiki/Ronald_L._Rivest">Ronald L. Rivest</A>; <A 
  href="http://en.wikipedia.org/wiki/Clifford_Stein">Clifford Stein</A> (2001). 
  <I><A 
  href="http://en.wikipedia.org/wiki/Introduction_to_Algorithms">Introduction to 
  Algorithms</A></I> (2e ed.). MIT Press and McGraw-Hill. pp.&nbsp;881–887. <A 
  title="International Standard Book Number" 
  href="http://en.wikipedia.org/wiki/International_Standard_Book_Number">ISBN</A>&nbsp;<A 
  title=Special:BookSources/0-262-03293-7 
  href="http://en.wikipedia.org/wiki/Special:BookSources/0-262-03293-7">0-262-03293-7</A>.</SPAN><SPAN 
  class=Z3988 
  title=ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rft.genre=book&amp;rft.btitle=%5B%5BIntroduction+to+Algorithms%5D%5D&amp;rft.aulast=Cormen&amp;rft.aufirst=Thomas+H.&amp;rft.au=Cormen%2C%26%2332%3BThomas+H.&amp;rft.date=2001&amp;rft.pages=pp.%26nbsp%3B881%E2%80%93887&amp;rft.edition=2e&amp;rft.pub=MIT+Press+and+McGraw-Hill&amp;rft.isbn=0-262-03293-7&amp;rfr_id=info:sid/en.wikipedia.org:RSA><SPAN 
  style="DISPLAY: none">&nbsp;</SPAN></SPAN> </LI></UL>
<H2><SPAN class=editsection>[<A title="Edit section: External links" 
href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit&amp;section=23">edit</A>]</SPAN> 
<SPAN class=mw-headline id=External_links>External links</SPAN></H2>
<UL>
  <LI>The Original RSA Patent as filed with the U.S. Patent Office by Rivest; 
  Ronald L. (Belmont, MA), Shamir; Adi (Cambridge, MA), Adleman; Leonard M. 
  (Arlington, MA), December 14, 1977, <B><SPAN><A class="external text" 
  href="http://www.google.com/patents?vid=4405829" rel=nofollow>U.S. Patent 
  4,405,829</A></SPAN></B>. 
  <LI><A class="external text" 
  href="http://www.rsasecurity.com/rsalabs/node.asp?id=2125" rel=nofollow>PKCS 
  #1: RSA Cryptography Standard</A> (<A class=mw-redirect 
  title="RSA Laboratories" 
  href="http://en.wikipedia.org/wiki/RSA_Laboratories">RSA Laboratories</A> 
  website) 
  <UL>
    <LI>The <I><A href="http://en.wikipedia.org/wiki/PKCS">PKCS</A> #1</I> <A 
    title=Standardization 
    href="http://en.wikipedia.org/wiki/Standardization">standard</A> 
    <I>"provides recommendations for the implementation of <A 
    href="http://en.wikipedia.org/wiki/Public-key_cryptography">public-key 
    cryptography</A> based on the <B>RSA</B> algorithm, covering the following 
    aspects: cryptographic <A class=mw-redirect title="Primitive type" 
    href="http://en.wikipedia.org/wiki/Primitive_type">primitives</A>; <A 
    href="http://en.wikipedia.org/wiki/Encryption">encryption</A> schemes; <A 
    title="Digital signature" 
    href="http://en.wikipedia.org/wiki/Digital_signature">signature</A> schemes 
    with appendix; <A class=mw-redirect title=ASN.1 
    href="http://en.wikipedia.org/wiki/ASN.1">ASN.1</A> syntax for representing 
    keys and for identifying the schemes"</I>. </LI></UL>
  <LI><A class="external text" href="http://www.di-mgt.com.au/rsa_alg.html" 
  rel=nofollow>Thorough walk through of RSA</A> 
  <LI><A class="external text" 
  href="http://www.muppetlabs.com/~breadbox/txt/rsa.html" rel=nofollow>Prime 
  Number Hide-And-Seek: How the RSA Cipher Works</A> 
  <LI><A class="external text" href="http://www.cacr.math.uwaterloo.ca/hac/" 
  rel=nofollow>Menezes, Oorschot, Vanstone, Scott: <I>Handbook of Applied 
  Cryptography</I> (free PDF downloads), see Chapter 8</A> 
  <LI><A class="external text" href="http://eprint.iacr.org/2006/351" 
  rel=nofollow>Onur Aciicmez, Cetin Kaya Koc, Jean-Pierre Seifert: <I>On the 
  Power of Simple Branch Prediction Analysis</I></A> 
  <LI><A class="external text" href="http://blog.cacert.org/2006/11/193.html" 
  rel=nofollow>A New Vulnerability In RSA Cryptography, CAcert NEWS Blog</A> 
  <LI><A class="external text" href="http://xyssl.org/code/source/rsa/" 
  rel=nofollow>Example of an RSA implementation with PKCS#1 padding (GPL source 
  code)</A> 
  <LI><A class="external text" 
  href="http://www.cryptography.com/resources/whitepapers/TimingAttacks.pdf" 
  rel=nofollow>Kocher's article about timing attacks</A> 
  <LI><A class="external text" href="http://www.gax.nl/wiskundePO/" 
  rel=nofollow>Online RSA encryption application</A> <SPAN class=languageicon 
  style="FONT-WEIGHT: bold; FONT-SIZE: 0.95em; COLOR: #555">(Dutch)</SPAN> 
  <LI><A class="external text" 
  href="http://cryptool.org/media/RSA/RSA-Flash-en/player.html" rel=nofollow>An 
  animated explanation of RSA with its mathematical background by CrypTool</A> 
  </LI></UL>
<TABLE class=navbox cellSpacing=0>
  <TBODY>
  <TR>
    <TD 
    style="PADDING-RIGHT: 2px; PADDING-LEFT: 2px; PADDING-BOTTOM: 2px; PADDING-TOP: 2px">
      <TABLE class=nowraplinks 
      style="BACKGROUND: none transparent scroll repeat 0% 0%; WIDTH: 100%" 
      cellSpacing=0>
        <TBODY>
        <TR>
          <TD class="navbox-list navbox-odd" 
          style="PADDING-RIGHT: 0px; PADDING-LEFT: 0px; PADDING-BOTTOM: 0px; WIDTH: 100%; PADDING-TOP: 0px" 
          colSpan=2>
            <DIV 
            style="PADDING-RIGHT: 0.25em; PADDING-LEFT: 0.25em; PADDING-BOTTOM: 0em; PADDING-TOP: 0em"></DIV>
            <TABLE class="nowraplinks navbox-subgroup" style="WIDTH: 100%" 
            cellSpacing=0>
              <TBODY>
              <TR>
                <TD class="navbox-list navbox-odd" 
                style="PADDING-RIGHT: 0px; PADDING-LEFT: 0px; PADDING-BOTTOM: 0px; WIDTH: 100%; PADDING-TOP: 0px" 
                colSpan=2>
                  <DIV 
                  style="PADDING-RIGHT: 0.25em; PADDING-LEFT: 0.25em; PADDING-BOTTOM: 0em; PADDING-TOP: 0em"></DIV>
                  <TABLE class="nowraplinks navbox-subgroup" style="WIDTH: 100%" 
                  cellSpacing=0>
                    <TBODY>
                    <TR>
                      <TH class=navbox-title style="BACKGROUND: #ccf" 
                        colSpan=2><SPAN 
                        style="FLOAT: left; WIDTH: 6em; TEXT-ALIGN: left"><SPAN 
                        class="noprint plainlinks navbar"><SPAN 
                        style="WORD-SPACING: -0.12em; WHITE-SPACE: nowrap"><A 
                        title="Template:Crypto public-key" 
                        href="http://en.wikipedia.org/wiki/Template:Crypto_public-key"><SPAN 
                        title="View this template" 
                        style="FONT-SIZE: 100%; BACKGROUND: none transparent scroll repeat 0% 0%; BORDER-TOP-STYLE: none; BORDER-RIGHT-STYLE: none; BORDER-LEFT-STYLE: none; BORDER-BOTTOM-STYLE: none">v</SPAN></A> 
                        <SPAN 
                        style="FONT-SIZE: 100%; BACKGROUND: none transparent scroll repeat 0% 0%; BORDER-TOP-STYLE: none; BORDER-RIGHT-STYLE: none; BORDER-LEFT-STYLE: none; BORDER-BOTTOM-STYLE: none"><B>·</B></SPAN> 
                        <A title="Template talk:Crypto public-key" 
                        href="http://en.wikipedia.org/wiki/Template_talk:Crypto_public-key"><SPAN 
                        title="Discuss this template" 
                        style="FONT-SIZE: 100%; BACKGROUND: none transparent scroll repeat 0% 0%; BORDER-TOP-STYLE: none; BORDER-RIGHT-STYLE: none; BORDER-LEFT-STYLE: none; BORDER-BOTTOM-STYLE: none">d</SPAN></A> 
                        <SPAN 
                        style="FONT-SIZE: 100%; BACKGROUND: none transparent scroll repeat 0% 0%; BORDER-TOP-STYLE: none; BORDER-RIGHT-STYLE: none; BORDER-LEFT-STYLE: none; BORDER-BOTTOM-STYLE: none"><B>·</B></SPAN> 
                        <A class="external text" 
                        href="http://en.wikipedia.org/w/index.php?title=Template:Crypto_public-key&amp;action=edit" 
                        rel=nofollow><SPAN title="Edit this template" 
                        style="FONT-SIZE: 100%; BACKGROUND: none transparent scroll repeat 0% 0%; BORDER-TOP-STYLE: none; BORDER-RIGHT-STYLE: none; BORDER-LEFT-STYLE: none; BORDER-BOTTOM-STYLE: none">e</SPAN></A></SPAN></SPAN></SPAN><SPAN 
                        style="FLOAT: right; WIDTH: 6em">&nbsp;</SPAN><SPAN 
                        class="" style="FONT-SIZE: 100%"><A 
                        href="http://en.wikipedia.org/wiki/Public-key_cryptography">Public-key 
                        cryptography</A></SPAN></TH></TR>
                    <TR style="HEIGHT: 2px">
                      <TD></TD></TR>
                    <TR>
                      <TD class=navbox-group>Algorithms</TD>
                      <TD class="navbox-list navbox-odd" 
                      style="PADDING-RIGHT: 0px; PADDING-LEFT: 0px; PADDING-BOTTOM: 0px; BORDER-LEFT: 2px solid; WIDTH: 100%; PADDING-TOP: 0px; TEXT-ALIGN: left">
                        <DIV 
                        style="PADDING-RIGHT: 0.25em; PADDING-LEFT: 0.25em; PADDING-BOTTOM: 0em; PADDING-TOP: 0em">
                        <P><SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Benaloh cryptosystem" 
                        href="http://en.wikipedia.org/wiki/Benaloh_cryptosystem">Benaloh</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Blum–Goldwasser cryptosystem" 
                        href="http://en.wikipedia.org/wiki/Blum–Goldwasser_cryptosystem">Blum–Goldwasser</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Cayley–Purser algorithm" 
                        href="http://en.wikipedia.org/wiki/Cayley–Purser_algorithm">Cayley–Purser</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        href="http://en.wikipedia.org/wiki/CEILIDH">CEILIDH</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Cramer–Shoup cryptosystem" 
                        href="http://en.wikipedia.org/wiki/Cramer–Shoup_cryptosystem">Cramer–Shoup</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Damgård–Jurik cryptosystem" 
                        href="http://en.wikipedia.org/wiki/Damgård–Jurik_cryptosystem">Damgård–Jurik</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Diffie–Hellman key exchange" 
                        href="http://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange">DH</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Digital Signature Algorithm" 
                        href="http://en.wikipedia.org/wiki/Digital_Signature_Algorithm">DSA</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Efficient Probabilistic Public-Key Encryption Scheme" 
                        href="http://en.wikipedia.org/wiki/Efficient_Probabilistic_Public-Key_Encryption_Scheme">EPOC</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Elliptic curve Diffie–Hellman" 
                        href="http://en.wikipedia.org/wiki/Elliptic_curve_Diffie–Hellman">ECDH</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Elliptic Curve DSA" 
                        href="http://en.wikipedia.org/wiki/Elliptic_Curve_DSA">ECDSA</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Encrypted key exchange" 
                        href="http://en.wikipedia.org/wiki/Encrypted_key_exchange">EKE</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap">ElGamal (<A 
                        title="ElGamal encryption" 
                        href="http://en.wikipedia.org/wiki/ElGamal_encryption">encryption</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="ElGamal signature scheme" 
                        href="http://en.wikipedia.org/wiki/ElGamal_signature_scheme">signature 
                        scheme</A>)&nbsp;<B>·</B></SPAN> <SPAN 
                        style="WHITE-SPACE: nowrap"><A 
                        title="GMR (cryptography)" 
                        href="http://en.wikipedia.org/wiki/GMR_(cryptography)">GMR</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Goldwasser–Micali cryptosystem" 
                        href="http://en.wikipedia.org/wiki/Goldwasser–Micali_cryptosystem">Goldwasser–Micali</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Hidden Field Equations" 
                        href="http://en.wikipedia.org/wiki/Hidden_Field_Equations">HFE</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Integrated Encryption Scheme" 
                        href="http://en.wikipedia.org/wiki/Integrated_Encryption_Scheme">IES</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Lamport signature" 
                        href="http://en.wikipedia.org/wiki/Lamport_signature">Lamport</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="McEliece cryptosystem" 
                        href="http://en.wikipedia.org/wiki/McEliece_cryptosystem">McEliece</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Merkle–Hellman knapsack cryptosystem" 
                        href="http://en.wikipedia.org/wiki/Merkle–Hellman_knapsack_cryptosystem">Merkle–Hellman</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        href="http://en.wikipedia.org/wiki/MQV">MQV</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Naccache–Stern cryptosystem" 
                        href="http://en.wikipedia.org/wiki/Naccache–Stern_cryptosystem">Naccache–Stern</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        href="http://en.wikipedia.org/wiki/NTRUEncrypt">NTRUEncrypt</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        href="http://en.wikipedia.org/wiki/NTRUSign">NTRUSign</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Paillier cryptosystem" 
                        href="http://en.wikipedia.org/wiki/Paillier_cryptosystem">Paillier</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Rabin cryptosystem" 
                        href="http://en.wikipedia.org/wiki/Rabin_cryptosystem">Rabin</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><STRONG 
                        class=selflink>RSA</STRONG>&nbsp;<B>·</B></SPAN> <SPAN 
                        style="WHITE-SPACE: nowrap"><A 
                        title="Okamoto–Uchiyama cryptosystem" 
                        href="http://en.wikipedia.org/wiki/Okamoto–Uchiyama_cryptosystem">Okamoto–Uchiyama</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Schnorr signature" 
                        href="http://en.wikipedia.org/wiki/Schnorr_signature">Schnorr</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Schmidt–Samoa cryptosystem" 
                        href="http://en.wikipedia.org/wiki/Schmidt–Samoa_cryptosystem">Schmidt–Samoa</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="SPEKE (cryptography)" 
                        href="http://en.wikipedia.org/wiki/SPEKE_(cryptography)">SPEKE</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Secure Remote Password protocol" 
                        href="http://en.wikipedia.org/wiki/Secure_Remote_Password_protocol">SRP</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Station-to-Station protocol" 
                        href="http://en.wikipedia.org/wiki/Station-to-Station_protocol">STS</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        href="http://en.wikipedia.org/wiki/Three-pass_protocol">Three-pass 
                        protocol</A>&nbsp;<B>·</B></SPAN> <SPAN 
                        style="WHITE-SPACE: nowrap"><A 
                        href="http://en.wikipedia.org/wiki/XTR">XTR</A></SPAN></P></DIV></TD></TR>
                    <TR style="HEIGHT: 2px">
                      <TD></TD></TR>
                    <TR>
                      <TD class=navbox-group>Theory</TD>
                      <TD class="navbox-list navbox-even" 
                      style="PADDING-RIGHT: 0px; PADDING-LEFT: 0px; PADDING-BOTTOM: 0px; BORDER-LEFT: 2px solid; WIDTH: 100%; PADDING-TOP: 0px; TEXT-ALIGN: left">
                        <DIV 
                        style="PADDING-RIGHT: 0.25em; PADDING-LEFT: 0.25em; PADDING-BOTTOM: 0em; PADDING-TOP: 0em">
                        <P><SPAN style="WHITE-SPACE: nowrap"><A 
                        href="http://en.wikipedia.org/wiki/Discrete_logarithm">Discrete 
                        logarithm</A>&nbsp;<B>·</B></SPAN> <SPAN 
                        style="WHITE-SPACE: nowrap"><A 
                        href="http://en.wikipedia.org/wiki/Elliptic_curve_cryptography">Elliptic 
                        curve cryptography</A>&nbsp;<B>·</B></SPAN> <SPAN 
                        style="WHITE-SPACE: nowrap"><A 
                        href="http://en.wikipedia.org/wiki/RSA_problem">RSA 
                        problem</A></SPAN></P></DIV></TD></TR>
                    <TR style="HEIGHT: 2px">
                      <TD></TD></TR>
                    <TR>
                      <TD class=navbox-group>Standardization</TD>
                      <TD class="navbox-list navbox-odd" 
                      style="PADDING-RIGHT: 0px; PADDING-LEFT: 0px; PADDING-BOTTOM: 0px; BORDER-LEFT: 2px solid; WIDTH: 100%; PADDING-TOP: 0px; TEXT-ALIGN: left">
                        <DIV 
                        style="PADDING-RIGHT: 0.25em; PADDING-LEFT: 0.25em; PADDING-BOTTOM: 0em; PADDING-TOP: 0em">
                        <P><SPAN style="WHITE-SPACE: nowrap"><A class=new 
                        title="ANS X9F1 (page does not exist)" 
                        href="http://en.wikipedia.org/w/index.php?title=ANS_X9F1&amp;action=edit&amp;redlink=1">ANS 
                        X9F1</A>&nbsp;<B>·</B></SPAN> <SPAN 
                        style="WHITE-SPACE: nowrap"><A 
                        href="http://en.wikipedia.org/wiki/CRYPTREC">CRYPTREC</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        href="http://en.wikipedia.org/wiki/IEEE_P1363">IEEE 
                        P1363</A>&nbsp;<B>·</B></SPAN> <SPAN 
                        style="WHITE-SPACE: nowrap"><A 
                        href="http://en.wikipedia.org/wiki/NESSIE">NESSIE</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="NSA Suite B Cryptography" 
                        href="http://en.wikipedia.org/wiki/NSA_Suite_B_Cryptography">NSA 
                        Suite B</A></SPAN></P></DIV></TD></TR>
                    <TR style="HEIGHT: 2px">
                      <TD></TD></TR>
                    <TR>
                      <TD class=navbox-group>Topics</TD>
                      <TD class="navbox-list navbox-even" 
                      style="PADDING-RIGHT: 0px; PADDING-LEFT: 0px; PADDING-BOTTOM: 0px; BORDER-LEFT: 2px solid; WIDTH: 100%; PADDING-TOP: 0px; TEXT-ALIGN: left">
                        <DIV 
                        style="PADDING-RIGHT: 0.25em; PADDING-LEFT: 0.25em; PADDING-BOTTOM: 0em; PADDING-TOP: 0em">
                        <P><SPAN style="WHITE-SPACE: nowrap"><A 
                        href="http://en.wikipedia.org/wiki/Digital_signature">Digital 
                        signature</A>&nbsp;<B>·</B></SPAN> <SPAN 
                        style="WHITE-SPACE: nowrap"><A class=mw-redirect 
                        title="Optimal Asymmetric Encryption Padding" 
                        href="http://en.wikipedia.org/wiki/Optimal_Asymmetric_Encryption_Padding">OAEP</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Public key fingerprint" 
                        href="http://en.wikipedia.org/wiki/Public_key_fingerprint">Fingerprint</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        title="Public key infrastructure" 
                        href="http://en.wikipedia.org/wiki/Public_key_infrastructure">PKI</A>&nbsp;<B>·</B></SPAN> 
                        <SPAN style="WHITE-SPACE: nowrap"><A 
                        href="http://en.wikipedia.org/wiki/Web_of_trust">Web of 
                        trust</A>&nbsp;<B>·</B></SPAN> <SPAN 
                        style="WHITE-SPACE: nowrap"><A 
                        href="http://en.wikipedia.org/wiki/Key_size">Key 
                        size</A></SPAN></P></DIV></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></TD></TR>
        <TR style="HEIGHT: 2px">
          <TD></TD></TR>
        <TR>
          <TD class="navbox-list navbox-even" 
          style="PADDING-RIGHT: 0px; PADDING-LEFT: 0px; PADDING-BOTTOM: 0px; WIDTH: 100%; PADDING-TOP: 0px" 
          colSpan=2>
            <DIV 
            style="PADDING-RIGHT: 0.25em; PADDING-LEFT: 0.25em; PADDING-BOTTOM: 0em; PADDING-TOP: 0em"></DIV>
            <TABLE class="nowraplinks navbox-subgroup" style="WIDTH: 100%" 
            cellSpacing=0>
              <TBODY>
              <TR>
                <TH class=navbox-title style="BACKGROUND: #ccf" 
                  colSpan=2><SPAN 
                  style="FLOAT: left; WIDTH: 6em; TEXT-ALIGN: left"><SPAN 
                  class="noprint plainlinks navbar"><SPAN 
                  style="WORD-SPACING: -0.12em; WHITE-SPACE: nowrap"><A 
                  title="Template:Crypto navbox" 
                  href="http://en.wikipedia.org/wiki/Template:Crypto_navbox"><SPAN 
                  title="View this template" 
                  style="FONT-SIZE: 100%; BACKGROUND: none transparent scroll repeat 0% 0%; BORDER-TOP-STYLE: none; BORDER-RIGHT-STYLE: none; BORDER-LEFT-STYLE: none; BORDER-BOTTOM-STYLE: none">v</SPAN></A> 
                  <SPAN 
                  style="FONT-SIZE: 100%; BACKGROUND: none transparent scroll repeat 0% 0%; BORDER-TOP-STYLE: none; BORDER-RIGHT-STYLE: none; BORDER-LEFT-STYLE: none; BORDER-BOTTOM-STYLE: none"><B>·</B></SPAN> 
                  <A title="Template talk:Crypto navbox" 
                  href="http://en.wikipedia.org/wiki/Template_talk:Crypto_navbox"><SPAN 
                  title="Discuss this template" 
                  style="FONT-SIZE: 100%; BACKGROUND: none transparent scroll repeat 0% 0%; BORDER-TOP-STYLE: none; BORDER-RIGHT-STYLE: none; BORDER-LEFT-STYLE: none; BORDER-BOTTOM-STYLE: none">d</SPAN></A> 
                  <SPAN 
                  style="FONT-SIZE: 100%; BACKGROUND: none transparent scroll repeat 0% 0%; BORDER-TOP-STYLE: none; BORDER-RIGHT-STYLE: none; BORDER-LEFT-STYLE: none; BORDER-BOTTOM-STYLE: none"><B>·</B></SPAN> 
                  <A class="external text" 
                  href="http://en.wikipedia.org/w/index.php?title=Template:Crypto_navbox&amp;action=edit" 
                  rel=nofollow><SPAN title="Edit this template" 
                  style="FONT-SIZE: 100%; BACKGROUND: none transparent scroll repeat 0% 0%; BORDER-TOP-STYLE: none; BORDER-RIGHT-STYLE: none; BORDER-LEFT-STYLE: none; BORDER-BOTTOM-STYLE: none">e</SPAN></A></SPAN></SPAN></SPAN><SPAN 
                  style="FLOAT: right; WIDTH: 6em">&nbsp;</SPAN><SPAN class="" 
                  style="FONT-SIZE: 100%"><A 
                  href="http://en.wikipedia.org/wiki/Cryptography">Cryptography</A></SPAN></TH></TR>
              <TR style="HEIGHT: 2px">
                <TD></TD></TR>
              <TR>
                <TD class="navbox-list navbox-odd" 
                style="PADDING-RIGHT: 0px; PADDING-LEFT: 0px; PADDING-BOTTOM: 0px; WIDTH: 100%; PADDING-TOP: 0px" 
                colSpan=2>
                  <DIV 
                  style="PADDING-RIGHT: 0.25em; PADDING-LEFT: 0.25em; PADDING-BOTTOM: 0em; PADDING-TOP: 0em"><A 
                  href="http://en.wikipedia.org/wiki/History_of_cryptography">History 
                  of cryptography</A>&nbsp;<SPAN 
                  style="FONT-WEIGHT: bold">·</SPAN> <A 
                  href="http://en.wikipedia.org/wiki/Cryptanalysis">Cryptanalysis</A>&nbsp;<SPAN 
                  style="FONT-WEIGHT: bold">·</SPAN> <A 
                  title=Portal:Cryptography 
                  href="http://en.wikipedia.org/wiki/Portal:Cryptography">Cryptography 
                  portal</A>&nbsp;<SPAN style="FONT-WEIGHT: bold">·</SPAN> <A 
                  href="http://en.wikipedia.org/wiki/Outline_of_cryptography">Outline 
                  of cryptography</A></DIV></TD></TR>
              <TR style="HEIGHT: 2px">
                <TD></TD></TR>
              <TR>
                <TD class="navbox-list navbox-even" 
                style="PADDING-RIGHT: 0px; PADDING-LEFT: 0px; PADDING-BOTTOM: 0px; WIDTH: 100%; PADDING-TOP: 0px" 
                colSpan=2>
                  <DIV 
                  style="PADDING-RIGHT: 0.25em; PADDING-LEFT: 0.25em; PADDING-BOTTOM: 0em; PADDING-TOP: 0em"><A 
                  href="http://en.wikipedia.org/wiki/Symmetric-key_algorithm">Symmetric-key 
                  algorithm</A>&nbsp;<SPAN style="FONT-WEIGHT: bold">·</SPAN> <A 
                  href="http://en.wikipedia.org/wiki/Block_cipher">Block 
                  cipher</A>&nbsp;<SPAN style="FONT-WEIGHT: bold">·</SPAN> <A 
                  href="http://en.wikipedia.org/wiki/Stream_cipher">Stream 
                  cipher</A>&nbsp;<SPAN style="FONT-WEIGHT: bold">·</SPAN> <A 
                  href="http://en.wikipedia.org/wiki/Public-key_cryptography">Public-key 
                  cryptography</A>&nbsp;<SPAN style="FONT-WEIGHT: bold">·</SPAN> 
                  <A 
                  href="http://en.wikipedia.org/wiki/Cryptographic_hash_function">Cryptographic 
                  hash function</A>&nbsp;<SPAN 
                  style="FONT-WEIGHT: bold">·</SPAN> <A 
                  href="http://en.wikipedia.org/wiki/Message_authentication_code">Message 
                  authentication code</A>&nbsp;<SPAN 
                  style="FONT-WEIGHT: bold">·</SPAN> <A 
                  title="Cryptographically secure pseudorandom number generator" 
                  href="http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator">Random 
                  numbers</A>&nbsp;<SPAN style="FONT-WEIGHT: bold">·</SPAN> <A 
                  href="http://en.wikipedia.org/wiki/Steganography">Steganography</A></DIV></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE><!-- 
NewPP limit report
Preprocessor node count: 6062/1000000
Post-expand include size: 126356/2048000 bytes
Template argument size: 71860/2048000 bytes
Expensive parser function count: 2/500
--><!-- Saved in parser cache with key enwiki:pcache:idhash:25385-0!1!0!!en!4 and timestamp 20110217064419 -->
<DIV class=printfooter>Retrieved from "<A 
href="mhtml:file://E:\sve-air\documentacion\RSA - Wikipedia, the free encyclopedia.mht!http://en.wikipedia.org/wiki/RSA">http://en.wikipedia.org/wiki/RSA</A>"</DIV><!-- /bodytext --><!-- catlinks -->
<DIV class=catlinks id=catlinks>
<DIV id=mw-normal-catlinks><A title=Special:Categories 
href="http://en.wikipedia.org/wiki/Special:Categories">Categories</A>: <SPAN 
dir=ltr><A title="Category:Public-key cryptography" 
href="http://en.wikipedia.org/wiki/Category:Public-key_cryptography">Public-key 
cryptography</A></SPAN> | <SPAN dir=ltr><A 
title="Category:Asymmetric-key cryptosystems" 
href="http://en.wikipedia.org/wiki/Category:Asymmetric-key_cryptosystems">Asymmetric-key 
cryptosystems</A></SPAN> | <SPAN dir=ltr><A title="Category:Electronic commerce" 
href="http://en.wikipedia.org/wiki/Category:Electronic_commerce">Electronic 
commerce</A></SPAN></DIV>
<DIV class=mw-hidden-cats-hidden id=mw-hidden-catlinks>Hidden categories: <SPAN 
dir=ltr><A title="Category:All articles with unsourced statements" 
href="http://en.wikipedia.org/wiki/Category:All_articles_with_unsourced_statements">All 
articles with unsourced statements</A></SPAN> | <SPAN dir=ltr><A 
title="Category:Articles with unsourced statements from January 2009" 
href="http://en.wikipedia.org/wiki/Category:Articles_with_unsourced_statements_from_January_2009">Articles 
with unsourced statements from January 2009</A></SPAN> | <SPAN dir=ltr><A 
title="Category:Articles containing potentially dated statements from 2010" 
href="http://en.wikipedia.org/wiki/Category:Articles_containing_potentially_dated_statements_from_2010">Articles 
containing potentially dated statements from 2010</A></SPAN> | <SPAN dir=ltr><A 
title="Category:All articles containing potentially dated statements" 
href="http://en.wikipedia.org/wiki/Category:All_articles_containing_potentially_dated_statements">All 
articles containing potentially dated statements</A></SPAN> | <SPAN dir=ltr><A 
title="Category:Articles with Alice and Bob explanations" 
href="http://en.wikipedia.org/wiki/Category:Articles_with_Alice_and_Bob_explanations">Articles 
with Alice and Bob explanations</A></SPAN></DIV></DIV><!-- /catlinks -->
<DIV class=visualClear></DIV></DIV><!-- /bodyContent --></DIV><!-- /content --><!-- header -->
<DIV class=noprint id=mw-head><!-- 0 -->
<DIV class="" id=p-personal>
<H5>Personal tools</H5>
<UL>
  <LI id=pt-login><A 
  title="You are encouraged to log in; however, it is not mandatory. [o]" 
  accessKey=o 
  href="http://en.wikipedia.org/w/index.php?title=Special:UserLogin&amp;returnto=RSA">Log 
  in / create account</A> </LI></UL></DIV><!-- /0 -->
<DIV id=left-navigation><!-- 0 -->
<DIV class=vectorTabs id=p-namespaces>
<H5>Namespaces</H5>
<UL>
  <LI class=selected id=ca-nstab-main><SPAN><A title="View the content page [c]" 
  accessKey=c 
  href="mhtml:file://E:\sve-air\documentacion\RSA - Wikipedia, the free encyclopedia.mht!http://en.wikipedia.org/wiki/RSA">Article</A></SPAN> 
  </LI>
  <LI id=ca-talk><SPAN><A title="Discussion about the content page [t]" 
  accessKey=t href="http://en.wikipedia.org/wiki/Talk:RSA">Discussion</A></SPAN> 
  </LI></UL></DIV><!-- /0 --><!-- 1 -->
<DIV class="vectorMenu emptyPortlet" id=p-variants>
<H5><SPAN>Variants</SPAN><A href="http://en.wikipedia.org/wiki/RSA#"></A></H5>
<DIV class=menu>
<UL></UL></DIV></DIV><!-- /1 --></DIV>
<DIV id=right-navigation><!-- 0 -->
<DIV class=vectorTabs id=p-views>
<H5>Views</H5>
<UL>
  <LI class=selected id=ca-view><SPAN><A 
  href="mhtml:file://E:\sve-air\documentacion\RSA - Wikipedia, the free encyclopedia.mht!http://en.wikipedia.org/wiki/RSA">Read</A></SPAN> 
  </LI>
  <LI id=ca-edit><SPAN><A 
  title="You can edit this page. &#10;Please use the preview button before saving. [e]" 
  accessKey=e 
  href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=edit">Edit</A></SPAN> 
  </LI>
  <LI class="collapsible " id=ca-history><SPAN><A 
  title="Past versions of this page [h]" accessKey=h 
  href="http://en.wikipedia.org/w/index.php?title=RSA&amp;action=history">View 
  history</A></SPAN> </LI></UL></DIV><!-- /0 --><!-- 1 -->
<DIV class="vectorMenu emptyPortlet" id=p-cactions>
<H5><SPAN>Actions</SPAN><A href="http://en.wikipedia.org/wiki/RSA#"></A></H5>
<DIV class=menu>
<UL></UL></DIV></DIV><!-- /1 --><!-- 2 -->
<DIV id=p-search>
<H5><LABEL for=searchInput>Search</LABEL></H5>
<FORM id=searchform action=/w/index.php><INPUT type=hidden value=Special:Search 
name=title> 
<DIV id=simpleSearch><INPUT id=searchInput title="Search Wikipedia [f]" 
accessKey=f name=search><BUTTON id=searchButton 
title="Search Wikipedia for this text" name=button type=submit><IMG alt=Search 
src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht18F(1).tmp"></BUTTON> 
</DIV></FORM></DIV><!-- /2 --></DIV></DIV><!-- /header --><!-- panel -->
<DIV class=noprint id=mw-panel><!-- logo -->
<DIV id=p-logo><A title="Visit the main page" 
style="BACKGROUND-IMAGE: url(http://upload.wikimedia.org/wikipedia/en/b/bc/Wiki.png)" 
href="http://en.wikipedia.org/wiki/Main_Page"></A></DIV><!-- /logo --><!-- navigation -->
<DIV class=portal id=p-navigation>
<H5>Navigation</H5>
<DIV class=body>
<UL>
  <LI id=n-mainpage-description><A title="Visit the main page [z]" accessKey=z 
  href="http://en.wikipedia.org/wiki/Main_Page">Main page</A> </LI>
  <LI id=n-contents><A title="Guides to browsing Wikipedia" 
  href="http://en.wikipedia.org/wiki/Portal:Contents">Contents</A> </LI>
  <LI id=n-featuredcontent><A title="Featured content – the best of Wikipedia" 
  href="http://en.wikipedia.org/wiki/Portal:Featured_content">Featured 
  content</A> </LI>
  <LI id=n-currentevents><A 
  title="Find background information on current events" 
  href="http://en.wikipedia.org/wiki/Portal:Current_events">Current events</A> 
  </LI>
  <LI id=n-randompage><A title="Load a random article [x]" accessKey=x 
  href="http://en.wikipedia.org/wiki/Special:Random">Random article</A> </LI>
  <LI id=n-sitesupport><A title="Support us" 
  href="http://wikimediafoundation.org/wiki/Special:Landingcheck?landing_page=WMFJA085&amp;language=en&amp;utm_source=donate&amp;utm_medium=sidebar&amp;utm_campaign=20101204SB002">Donate 
  to Wikipedia</A> </LI></UL></DIV></DIV><!-- /navigation --><!-- SEARCH --><!-- /SEARCH --><!-- interaction -->
<DIV class=portal id=p-interaction>
<H5>Interaction</H5>
<DIV class=body>
<UL>
  <LI id=n-help><A title="Guidance on how to use and edit Wikipedia" 
  href="http://en.wikipedia.org/wiki/Help:Contents">Help</A> </LI>
  <LI id=n-aboutsite><A title="Find out about Wikipedia" 
  href="http://en.wikipedia.org/wiki/Wikipedia:About">About Wikipedia</A> </LI>
  <LI id=n-portal><A 
  title="About the project, what you can do, where to find things" 
  href="http://en.wikipedia.org/wiki/Wikipedia:Community_portal">Community 
  portal</A> </LI>
  <LI id=n-recentchanges><A title="The list of recent changes in the wiki [r]" 
  accessKey=r href="http://en.wikipedia.org/wiki/Special:RecentChanges">Recent 
  changes</A> </LI>
  <LI id=n-contact><A title="How to contact Wikipedia" 
  href="http://en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</A> 
  </LI></UL></DIV></DIV><!-- /interaction --><!-- TOOLBOX -->
<DIV class=portal id=p-tb>
<H5>Toolbox</H5>
<DIV class=body>
<UL>
  <LI id=t-whatlinkshere><A 
  title="List of all English Wikipedia pages containing links to this page [j]" 
  accessKey=j href="http://en.wikipedia.org/wiki/Special:WhatLinksHere/RSA">What 
  links here</A> </LI>
  <LI id=t-recentchangeslinked><A 
  title="Recent changes in pages linked from this page [k]" accessKey=k 
  href="http://en.wikipedia.org/wiki/Special:RecentChangesLinked/RSA">Related 
  changes</A> </LI>
  <LI id=t-upload><A title="Upload files [u]" accessKey=u 
  href="http://en.wikipedia.org/wiki/Wikipedia:Upload">Upload file</A> </LI>
  <LI id=t-specialpages><A title="List of all special pages [q]" accessKey=q 
  href="http://en.wikipedia.org/wiki/Special:SpecialPages">Special pages</A> 
  </LI>
  <LI id=t-permalink><A title="Permanent link to this revision of the page" 
  href="http://en.wikipedia.org/w/index.php?title=RSA&amp;oldid=413937646">Permanent 
  link</A> </LI>
  <LI id=t-cite><A title="Information on how to cite this page" 
  href="http://en.wikipedia.org/w/index.php?title=Special:Cite&amp;page=RSA&amp;id=413937646">Cite 
  this page</A> </LI></UL></DIV></DIV><!-- /TOOLBOX --><!-- coll-print_export -->
<DIV class=portal id=p-coll-print_export>
<H5>Print/export</H5>
<DIV class=body>
<UL id=collectionPortletList>
  <LI id=coll-create_a_book><A title="Create a book or page collection" 
  href="http://en.wikipedia.org/w/index.php?title=Special:Book&amp;bookcmd=book_creator&amp;referer=RSA" 
  rel=nofollow>Create a book</A> </LI>
  <LI id=coll-download-as-rl><A title="Download a PDF version of this wiki page" 
  href="http://en.wikipedia.org/w/index.php?title=Special:Book&amp;bookcmd=render_article&amp;arttitle=RSA&amp;oldid=413937646&amp;writer=rl" 
  rel=nofollow>Download as PDF</A> </LI>
  <LI id=t-print><A title="Printable version of this page [p]" accessKey=p 
  href="http://en.wikipedia.org/w/index.php?title=RSA&amp;printable=yes">Printable 
  version</A></LI></UL></DIV></DIV><!-- /coll-print_export --><!-- LANGUAGES -->
<DIV class=portal id=p-lang>
<H5>Languages</H5>
<DIV class=body>
<UL>
  <LI class=interwiki-ar><A title="خوارزمية آر إس إيه" 
  href="http://ar.wikipedia.org/wiki/%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D8%A2%D8%B1_%D8%A5%D8%B3_%D8%A5%D9%8A%D9%87">العربية</A> 
  </LI>
  <LI class=interwiki-bg><A title=RSA 
  href="http://bg.wikipedia.org/wiki/RSA">Български</A> </LI>
  <LI class=interwiki-ca><A title=RSA 
  href="http://ca.wikipedia.org/wiki/RSA">Català</A> </LI>
  <LI class=interwiki-cs><A title=RSA 
  href="http://cs.wikipedia.org/wiki/RSA">Česky</A> </LI>
  <LI class=interwiki-da><A title=RSA 
  href="http://da.wikipedia.org/wiki/RSA">Dansk</A> </LI>
  <LI class=interwiki-de><A title=RSA-Kryptosystem 
  href="http://de.wikipedia.org/wiki/RSA-Kryptosystem">Deutsch</A> </LI>
  <LI class=interwiki-et><A title="RSA (algoritm)" 
  href="http://et.wikipedia.org/wiki/RSA_(algoritm)">Eesti</A> </LI>
  <LI class=interwiki-el><A title=RSA 
  href="http://el.wikipedia.org/wiki/RSA">Ελληνικά</A> </LI>
  <LI class=interwiki-es><A title=RSA 
  href="http://es.wikipedia.org/wiki/RSA">Español</A> </LI>
  <LI class=interwiki-eo><A title=RSA 
  href="http://eo.wikipedia.org/wiki/RSA">Esperanto</A> </LI>
  <LI class=interwiki-eu><A title=RSA 
  href="http://eu.wikipedia.org/wiki/RSA">Euskara</A> </LI>
  <LI class=interwiki-fa><A title=آراس‌ای 
  href="http://fa.wikipedia.org/wiki/%D8%A2%D8%B1%D8%A7%D8%B3%E2%80%8C%D8%A7%DB%8C">فارسی</A> 
  </LI>
  <LI class=interwiki-fr><A title="Rivest Shamir Adleman" 
  href="http://fr.wikipedia.org/wiki/Rivest_Shamir_Adleman">Français</A> </LI>
  <LI class=interwiki-gl><A title=RSA 
  href="http://gl.wikipedia.org/wiki/RSA">Galego</A> </LI>
  <LI class=interwiki-ko><A title="RSA 암호" 
  href="http://ko.wikipedia.org/wiki/RSA_%EC%95%94%ED%98%B8">한국어</A> </LI>
  <LI class=interwiki-hr><A title=RSA 
  href="http://hr.wikipedia.org/wiki/RSA">Hrvatski</A> </LI>
  <LI class=interwiki-id><A title=RSA 
  href="http://id.wikipedia.org/wiki/RSA">Bahasa Indonesia</A> </LI>
  <LI class=interwiki-is><A title=RSA 
  href="http://is.wikipedia.org/wiki/RSA">Íslenska</A> </LI>
  <LI class=interwiki-it><A title=RSA 
  href="http://it.wikipedia.org/wiki/RSA">Italiano</A> </LI>
  <LI class=interwiki-he><A title=RSA 
  href="http://he.wikipedia.org/wiki/RSA">עברית</A> </LI>
  <LI class=interwiki-ka><A title="RSA ალგორითმი" 
  href="http://ka.wikipedia.org/wiki/RSA_%E1%83%90%E1%83%9A%E1%83%92%E1%83%9D%E1%83%A0%E1%83%98%E1%83%97%E1%83%9B%E1%83%98">ქართული</A> 
  </LI>
  <LI class=interwiki-lv><A title="RSA šifrēšanas algoritms" 
  href="http://lv.wikipedia.org/wiki/RSA_%C5%A1ifr%C4%93%C5%A1anas_algoritms">Latviešu</A> 
  </LI>
  <LI class=interwiki-lt><A title=RSA 
  href="http://lt.wikipedia.org/wiki/RSA">Lietuvių</A> </LI>
  <LI class=interwiki-hu><A title=RSA-eljárás 
  href="http://hu.wikipedia.org/wiki/RSA-eljárás">Magyar</A> </LI>
  <LI class=interwiki-nl><A title="RSA (cryptografie)" 
  href="http://nl.wikipedia.org/wiki/RSA_(cryptografie)">Nederlands</A> </LI>
  <LI class=interwiki-ja><A title=RSA暗号 
  href="http://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7">日本語</A> </LI>
  <LI class=interwiki-no><A title=RSA 
  href="http://no.wikipedia.org/wiki/RSA">‪Norsk (bokmål)‬</A> </LI>
  <LI class=interwiki-pl><A title="RSA (kryptografia)" 
  href="http://pl.wikipedia.org/wiki/RSA_(kryptografia)">Polski</A> </LI>
  <LI class=interwiki-pt><A title=RSA 
  href="http://pt.wikipedia.org/wiki/RSA">Português</A> </LI>
  <LI class=interwiki-ro><A title=RSA 
  href="http://ro.wikipedia.org/wiki/RSA">Română</A> </LI>
  <LI class=interwiki-ru><A title=RSA 
  href="http://ru.wikipedia.org/wiki/RSA">Русский</A> </LI>
  <LI class=interwiki-simple><A title=RSA 
  href="http://simple.wikipedia.org/wiki/RSA">Simple English</A> </LI>
  <LI class=interwiki-sl><A title=RSA 
  href="http://sl.wikipedia.org/wiki/RSA">Slovenščina</A> </LI>
  <LI class=interwiki-sr><A title=RSA 
  href="http://sr.wikipedia.org/wiki/RSA">Српски / Srpski</A> </LI>
  <LI class=interwiki-fi><A title=RSA 
  href="http://fi.wikipedia.org/wiki/RSA">Suomi</A> </LI>
  <LI class=interwiki-sv><A title=RSA 
  href="http://sv.wikipedia.org/wiki/RSA">Svenska</A> </LI>
  <LI class=interwiki-th><A title=RSA 
  href="http://th.wikipedia.org/wiki/RSA">ไทย</A> </LI>
  <LI class=interwiki-tr><A title=RSA 
  href="http://tr.wikipedia.org/wiki/RSA">Türkçe</A> </LI>
  <LI class=interwiki-uk><A title=RSA 
  href="http://uk.wikipedia.org/wiki/RSA">Українська</A> </LI>
  <LI class=interwiki-vi><A title="RSA (mã hóa)" 
  href="http://vi.wikipedia.org/wiki/RSA_(mã_hóa)">Tiếng Việt</A> </LI>
  <LI class=interwiki-zh><A title=RSA加密演算法 
  href="http://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95">中文</A> 
  </LI></UL></DIV></DIV><!-- /LANGUAGES --></DIV><!-- /panel --><!-- footer -->
<DIV id=footer>
<UL id=footer-info>
  <LI id=footer-info-lastmod>This page was last modified on 14 February 2011 at 
  20:34.<BR>
  <LI id=footer-info-copyright>Text is available under the <A 
  href="http://en.wikipedia.org/wiki/Wikipedia:Text_of_Creative_Commons_Attribution-ShareAlike_3.0_Unported_License" 
  rel=license>Creative Commons Attribution-ShareAlike License</A><A 
  style="DISPLAY: none" href="http://creativecommons.org/licenses/by-sa/3.0/" 
  rel=license></A>; additional terms may apply. See <A 
  href="http://wikimediafoundation.org/wiki/Terms_of_Use">Terms of Use</A> for 
  details.<BR>Wikipedia® is a registered trademark of the <A 
  href="http://www.wikimediafoundation.org/">Wikimedia Foundation, Inc.</A>, a 
  non-profit organization.<BR>
  <LI class=noprint><A class=internal 
  href="http://en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact us</A> 
</LI></UL>
<UL id=footer-places>
  <LI id=footer-places-privacy><A title="wikimedia:Privacy policy" 
  href="http://wikimediafoundation.org/wiki/Privacy_policy">Privacy policy</A> 
  </LI>
  <LI id=footer-places-about><A title=Wikipedia:About 
  href="http://en.wikipedia.org/wiki/Wikipedia:About">About Wikipedia</A> </LI>
  <LI id=footer-places-disclaimer><A title="Wikipedia:General disclaimer" 
  href="http://en.wikipedia.org/wiki/Wikipedia:General_disclaimer">Disclaimers</A> 
  </LI></UL>
<UL class=noprint id=footer-icons>
  <LI id=footer-copyrightico><A href="http://wikimediafoundation.org/"><IMG 
  height=31 alt="Wikimedia Foundation" 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht192(1).tmp" 
  width=88></A> </LI>
  <LI id=footer-poweredbyico><A href="http://www.mediawiki.org/"><IMG height=31 
  alt="Powered by MediaWiki" 
  src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/mht195(1).tmp" 
  width=88></A> </LI></UL>
<DIV style="CLEAR: both"></DIV></DIV><!-- /footer -->
<SCRIPT src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/load.php" 
type=text/javascript></SCRIPT>

<SCRIPT type=text/javascript>if ( window.mediaWiki ) {
	mediaWiki.config.set({"wgCanonicalNamespace": "", "wgCanonicalSpecialPageName": false, "wgNamespaceNumber": 0, "wgPageName": "RSA", "wgTitle": "RSA", "wgAction": "view", "wgArticleId": 25385, "wgIsArticle": true, "wgUserName": null, "wgUserGroups": ["*"], "wgCurRevisionId": 413937646, "wgCategories": ["All articles with unsourced statements", "Articles with unsourced statements from January 2009", "Articles containing potentially dated statements from 2010", "All articles containing potentially dated statements", "Public-key cryptography", "Asymmetric-key cryptosystems", "Electronic commerce", "Articles with Alice and Bob explanations"], "wgBreakFrames": false, "wgRestrictionEdit": [], "wgRestrictionMove": [], "wgSearchNamespaces": [0], "wgFlaggedRevsParams": {"tags": {"status": {"levels": 1, "quality": 2, "pristine": 3}}}, "wgStableRevisionId": null, "wgRevContents": {"error": "Unable to get content.", "waiting": "Waiting for content"}, "wgWikimediaMobileUrl": "http://en.m.wikipedia.org/wiki", "wgCollapsibleNavBucketTest": false, "wgCollapsibleNavForceNewVersion": false, "wgArticleAssessmentJUIPath": "http://bits.wikimedia.org/w/extensions-1.17/UsabilityInitiative/js/js2stopgap/jui.combined.min.js", "Geo": {"city": "", "country": ""}, "wgNoticeProject": "wikipedia"});
}
</SCRIPT>

<SCRIPT type=text/javascript>if ( window.mediaWiki ) {
	mediaWiki.loader.load(["mediawiki.legacy.wikibits", "mediawiki.util", "mediawiki.legacy.ajax", "mediawiki.legacy.mwsuggest", "ext.vector.collapsibleNav", "ext.vector.collapsibleTabs", "ext.vector.editWarning", "ext.vector.simpleSearch"]);
	mediaWiki.loader.go();
}
</SCRIPT>

<SCRIPT 
src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/MobileRedirect.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/index.php" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/load(1).php" 
type=text/javascript></SCRIPT>

<SCRIPT type=text/javascript>if ( window.mediaWiki ) {
	mediaWiki.user.options.set({"ccmeonemails":0,"cols":80,"contextchars":50,"contextlines":5,"date":"default","diffonly":0,"disablemail":0,"disablesuggest":0,"editfont":"default","editondblclick":0,"editsection":1,"editsectiononrightclick":0,"enotifminoredits":0,"enotifrevealaddr":0,"enotifusertalkpages":1,"enotifwatchlistpages":0,"extendwatchlist":0,"externaldiff":0,"externaleditor":0,"fancysig":0,"forceeditsummary":0,"gender":"unknown","hideminor":0,"hidepatrolled":0,"highlightbroken":1,"imagesize":2,"justify":0,"math":1,"minordefault":0,"newpageshidepatrolled":0,"nocache":0,"noconvertlink":0,"norollbackdiff":0,"numberheadings":0,"previewonfirst":0,"previewontop":1,"quickbar":1,"rcdays":7,"rclimit":50,"rememberpassword":0,"rows":25,"searchlimit":20,"showhiddencats":0,"showjumplinks":1,"shownumberswatching":1,"showtoc":1,"showtoolbar":1,"skin":"vector","stubthreshold":0,"thumbsize":4,"underline":2,"uselivepreview":0,"usenewrc":0,"watchcreations":1,"watchdefault":0,"watchdeletion":0,"watchlistdays":"3","watchlisthideanons":0,"watchlisthidebots":0,"watchlisthideliu":0,"watchlisthideminor":0,"watchlisthideown":0,"watchlisthidepatrolled":0,"watchmoves":0,"wllimit":250,"flaggedrevssimpleui":1,"flaggedrevsstable":false,"flaggedrevseditdiffs":true,"flaggedrevsviewdiffs":false,"vector-simplesearch":1,"useeditwarning":1,"vector-collapsiblenav":1,"usebetatoolbar":1,"usebetatoolbar-cgd":1,"variant":"en","language":"en","searchNs0":true,"searchNs1":false,"searchNs2":false,"searchNs3":false,"searchNs4":false,"searchNs5":false,"searchNs6":false,"searchNs7":false,"searchNs8":false,"searchNs9":false,"searchNs10":false,"searchNs11":false,"searchNs12":false,"searchNs13":false,"searchNs14":false,"searchNs15":false,"searchNs100":false,"searchNs101":false,"searchNs108":false,"searchNs109":false});
	mediaWiki.loader.state({"user.options":"ready"});
}
</SCRIPT>

<SCRIPT 
src="RSA%20-%20Wikipedia,%20the%20free%20encyclopedia_archivos/geoiplookup_wikimedia_org" 
type=text/javascript></SCRIPT>
<!-- fixalpha -->
<SCRIPT type=text/javascript> if ( window.isMSIE55 ) fixalpha(); </SCRIPT>
<!-- /fixalpha --><!-- Served by srv197 in 0.054 secs. --></BODY></HTML>
